BrewlearnHeaps in Java
Binary heap operations and top-K problems with PriorityQueue.
A tree in an array
A binary heap is a complete binary tree stored in an array. In a min-heap, each parent is no larger than its children, so the smallest element sits at index 0. No pointers needed: children of i are at 2i + 1 and 2i + 2, and the parent of i is at (i - 1) / 2.
// 1 index: 0
// / \
// 4 8 index: 1, 2
// /
// 6 index: 3
// array: [1, 4, 8, 6]Sift up, sift down
offer: add at the end, then swap upward while smaller than the parent. poll: remove the root, move the last element to the root, then swap it down. Both move one level per step: O(log n). peek just reads index 0: O(1). But contains must scan the array: O(n).
Watch the array
What does this print?
var pq = new PriorityQueue<Integer>();
for (int x : new int[]{4, 6, 2}) pq.offer(x);
System.out.println(pq);
System.out.println(pq.poll() + " " + pq);[2, 6, 4] 2 [4, 6][2, 4, 6] 2 [4, 6][2, 6, 4] 2 [6, 4]
Show the answer
Round 1: [4]. Round 2: 6 goes to index 1, no swap: [4, 6]. Round 3: 2 goes to index 2 and sifts up past 4: [2, 6, 4]. poll removes 2, moves the last element (4) to the root; 4 < 6, so it stays: [4, 6].
Printing a heap isn't sorting it
toString and iteration walk the backing array, which is only partly ordered: only the root is guaranteed to be the minimum. To get sorted order, poll repeatedly: each poll removes the current smallest, so draining a min-heap yields ascending order. That's heap sort, O(n log n) for n polls.
var pq = new PriorityQueue<Integer>();
for (int x : new int[]{6, 2, 9, 1}) pq.offer(x);
System.out.println(pq); // [1, 2, 9, 6]
while (!pq.isEmpty())
System.out.print(pq.poll() + " ");
// 1 2 6 9Max-heaps
Java's PriorityQueue is a binary min-heap by default. For a max-heap, pass a comparator that reverses the order. Now the largest element is at the root.
var maxHeap = new PriorityQueue<Integer>(
Comparator.reverseOrder());
maxHeap.addAll(List.of(5, 1, 8));
maxHeap.poll(); // 8Top 100 of 10 million
List<Integer> all = new ArrayList<>(scores);
Collections.sort(all);
// take the last 100O(n log n) time and O(n) memory, sorting millions you'll throw away. A max-heap of everything has the same memory problem.
var top = new PriorityQueue<Integer>();
for (int s : scores) {
top.offer(s);
if (top.size() > 100) top.poll();
}O(n log K) time and only O(K) memory.
Why a MIN-heap for the LARGEST?
To keep the top 100 scores, we used a min-heap. Why not a max-heap?
Think about it, then reveal the answer
The min-heap's root is the weakest of the current top 100. That's exactly the one to evict when a better score arrives, and poll removes it in O(log K).
Heaps on the job
Task schedulers, rate limiters, "next event" timers, merging k sorted files, and Dijkstra's shortest paths all run on priority queues. Top-K with a bounded heap is one of the most common interview patterns.
Key takeaways
- Children of index i are at 2i + 1 and 2i + 2
- peek O(1); offer and poll O(log n)
- Iterating or printing a PriorityQueue is NOT sorted
- Top-K largest: keep a min-heap of size K
💡 A heap is a tournament bracket: the champion is always on top, but the rest is only partly ranked.
The binary heap was introduced by J. W. J. Williams in 1964 as the data structure behind his new sorting algorithm, heapsort.
Practice questions
What does this print?
var pq = new PriorityQueue<Integer>();
pq.addAll(List.of(7, 3, 9, 1));
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}- 7 3 9 1
- 9 7 3 1
- 1 7 3 9
- 1 3 7 9
Check your answer
1 3 7 9. Every poll removes the root of the min-heap, the current smallest, then restores the heap. Draining it yields ascending order (that's heap sort).
What does this print?
var pq = new PriorityQueue<Integer>();
for (int x : new int[]{5, 3, 8, 1}) pq.offer(x);
System.out.println(pq);- [1, 3, 5, 8]
- [1, 3, 8, 5]
- [5, 3, 8, 1]
- [8, 5, 3, 1]
Check your answer
[1, 3, 8, 5]. toString shows the backing array. 1 was added at index 3 and sifted up, swapping with 5 and then with 3 to reach the root. Only the root is guaranteed to be the minimum.