Priority Queues

A priority queue serves elements by priority rather than by arrival order. It is an abstract data type — a contract, not an implementation — and the implementation is almost always a binary heap.

The contract

Compare a plain queue, where the order out is the order in. Here every element carries a priority and the queue always serves the best one — a hospital triage list rather than a supermarket line.

Why a heap and not something simpler

The two arrays each make one operation free by making the other linear. A balanced tree matches the heap's complexity, but it maintains a total ordering nobody asked for — a priority queue never needs to know the third-smallest element. The heap maintains exactly the invariant the contract needs and nothing more, so it wins on constant factors and on memory: a flat array with no nodes and no references.

In Java

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
Check.eq(pq.poll(), 1, "min-heap by default - smallest first, not first added");

Min-heap by default, ordered by natural ordering. For a max-heap, or any other rule, supply a comparator:

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// By a field, then by another as a tie-break
PriorityQueue<Task> tasks = new PriorityQueue<>(
        Comparator.comparingInt(Task::priority).thenComparing(Task::name));

The comparator is the only difference between a min-heap and a max-heap. There is no separate class and no flag.

⚠️ Three things that surprise people

1. Iteration is not sorted. The heap property only guarantees the root, so for (var x : queue) walks the backing array in heap order, and queue.toString() prints that array. This looks like a bug and is not. The only way to get sorted order is to poll() until it is empty — which drains the queue.

2. remove(Object) is O(n). Removing the head is O(log n), but removing some arbitrary element means finding it first, and a heap has no way to search. If you need to remove or reprioritise arbitrary elements, a heap is the wrong structure — you want an indexed priority queue, or a TreeSet.

3. Changing an element's priority after inserting it corrupts the queue. The heap was arranged using the old value and nothing re-sorts it, so the element sits in the wrong place and the queue quietly returns the wrong "best". It is the same failure as mutating a key in a HashMap. Remove, change, and re-add — or make the priority immutable.

Top k without sorting

The pattern worth knowing, and the most common real use.

For the k largest elements, keep a min-heap of size k. The smallest of your current best k sits at the root, so each new element is one comparison away from a decision: bigger than the root, swap it in; otherwise discard.

        PriorityQueue<Integer> topK = new PriorityQueue<>();
        for (int value : values) {
            topK.add(value);
            if (topK.size() > k) {
                topK.poll();          // drop the smallest of the k+1
            }
        }
        Check.eq(topK.poll(), 7, "third largest");

O(n log k) time and O(k) space, against O(n log n) and O(n) for sorting everything. With n a billion and k = 10 that is the difference between a heap of ten integers and a sort that does not fit in memory.

The inversion is the part people get backwards: min-heap for top-k-largest, max-heap for top-k-smallest. You keep the heap ordered so that the element you are most willing to throw away is the one you can see.

The same idea, implemented directly on the heap from the previous post:

        MinHeap heap = heapify(values);
        int n = Math.min(k, values.length);
        int[] out = new int[n];
        for (int i = 0; i < n; i++) {
            out[i] = heap.poll();
        }
        return out;

Where they show up

• Dijkstra's shortest path — always expand the nearest unvisited vertex.
• A* search — the same, ordered by estimated total cost.
• Task scheduling — run the highest-priority job next.
• Event simulation — process the earliest event next.
• Huffman coding — repeatedly merge the two least frequent symbols.
• Merging k sorted lists — a heap of the k current heads.

The common shape: repeatedly take the best remaining option. Whenever a greedy algorithm needs the best next choice, a priority queue is how it gets it in O(log n) instead of O(n).

Concurrency

PriorityQueue is not thread-safe. PriorityBlockingQueue is the concurrent version, and DelayQueue is a priority queue ordered by expiry time — the head is not available until its delay has elapsed, which is how scheduled executors work.

What to remember

• An abstract type; a heap is the implementation that fits its contract exactly.
• Min-heap by default in Java; the comparator is the only thing that changes that.
• Iteration is not sorted, and it is not a bug.
• remove(Object) is O(n); do not mutate priorities in place.
• Top k largest → min-heap of size k. O(n log k) and O(k) space.