How does PriorityQueue work, and how do you use it to find the top K elements?

PriorityQueue is a binary heap. By default it is a min-heap: poll() always removes the smallest element. Passing Comparator.reverseOrder() makes it a max-heap. To find the K largest elements efficiently, keep a min-heap of size K: add each element, and when the heap grows beyond K, remove the smallest.

Key Points: • offer() and poll() are O(log n). peek() is O(1). • Iterating over a PriorityQueue or printing it does NOT give sorted order. Only repeated poll() returns elements in priority order. • Elements must be Comparable, or you pass a Comparator. • Top K with a min-heap of size K costs O(n log K), which is better than sorting everything (O(n log n)) when K is small. • PriorityQueue isn't thread-safe. PriorityBlockingQueue is the concurrent version.

Code Example:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class TopKDemo {

    static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int n : nums) {
            minHeap.offer(n);
            if (minHeap.size() > k) minHeap.poll();     // drop the smallest
        }
        List<Integer> result = new ArrayList<>(minHeap);
        result.sort(Collections.reverseOrder());
        return result;
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> min = new PriorityQueue<>(List.of(5, 1, 8, 3, 9, 2));
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        max.addAll(List.of(5, 1, 8, 3, 9, 2));

        System.out.println("Min-heap poll: " + min.poll() + ", max-heap poll: " + max.poll());

        StringBuilder order = new StringBuilder();
        while (!min.isEmpty()) order.append(min.poll()).append(' ');
        System.out.println("Remaining, polled in order: " + order.toString().trim());

        int[] nums = {3, 2, 1, 5, 6, 4, 9, 7};
        System.out.println("Top 3: " + topK(nums, 3));
    }
}

Output:

Min-heap poll: 1, max-heap poll: 9 Remaining, polled in order: 2 3 5 8 9 Top 3: [9, 7, 6]

Good to Know: For objects, pass a comparator such as new PriorityQueue<>(Comparator.comparing(Task::priority)). Typical interview uses include top K frequent words, merging K sorted lists, scheduling tasks by priority, and Dijkstra's shortest-path algorithm.

Interview Tip: A concise interview answer is:

"PriorityQueue is a binary heap, a min-heap by default, with O(log n) offer and poll and O(1) peek; Comparator.reverseOrder() turns it into a max-heap. Iterating it isn't sorted, only polling is. For the top K largest elements, I keep a min-heap of size K and remove the smallest whenever it grows past K, which is O(n log K)."

Previous question: Why is ArrayDeque preferred over Stack and LinkedList for stacks and queues?

Next question: How do you use TreeMap and NavigableMap methods like floorKey, ceilingKey, headMap and subMap?

More Java Collections interview questions

All Java Collections questions