Java 58: PriorityQueue & the Binary Heap
easy⏱ 5 mincoursejava
Array-backed binary heap
A binary heap is a complete tree flattened into an array: for index i, children are at 2i+1 and 2i+2, parent at (i-1)/2. The heap invariant for a min-heap: every parent ≤ its children, so the minimum is always at index 0. No pointers, great cache locality — the array is the tree.
PriorityQueue<Integer> pq = new PriorityQueue<>(); // min-heap
pq.add(5); pq.add(1); pq.add(3);
pq.peek(); // 1 (smallest, O(1))
pq.poll(); // 1 (remove smallest, O(log n))
// max-heap: new PriorityQueue<>(Comparator.reverseOrder())
sift-up (insert) and sift-down (poll)
Insert: append at the end, then sift up — swap with the parent while it's smaller — O(log n). Poll: take index 0 (the min), move the last element to the root, then sift down — swap with the smaller child while it's bigger — O(log n). Both touch only one root-to-leaf path, which is why a heap beats sorting when you need just the top few.
Top-K with a bounded heap
To find the K smallest of N items in O(N log K) (not O(N log N)), keep a max-heap of size K: push each element; if size exceeds K, pop the largest. What remains is the K smallest. (Symmetrically, a min-heap of size K gives the K largest.) This is the standard streaming top-K technique — you never hold all N sorted.
Build a min-heap, then heapsort
Implement MinHeap with push (sift-up) and pop (sift-down) over an array. Push [5, 3, 8, 1, 9, 2] and confirm peek() is 1. Then repeatedly pop() until empty to get a sorted ascending sequence 1 2 3 5 8 9 (that's heapsort). Print the peek, the sorted output, and the internal array after the pushes to show it is not fully sorted, only heap-ordered.
Don't iterate a PriorityQueue expecting order
for (x : pq) and pq.toArray() traverse the internal array, which is heap-ordered, not sorted — only the head is guaranteed smallest. To consume in sorted order you must poll repeatedly (which empties it) or copy to a list and sort. This trips up many in interviews.
Quiz: complexity of peek vs poll
What are the time complexities of PriorityQueue.peek() and poll()? peek is O(1) (the min is always at index 0); poll is O(log n) (it must move the last element to the root and sift it down to restore the heap invariant). Insert (add) is also O(log n).