PHASE 9Intermediate Java 5+ ~32 min· topic 8 of 13

Topic 9.8

PriorityQueue

In one line

PriorityQueue always hands out the smallest element first (or the largest, with a reversed comparator). It's a binary heap stored in an array: peek is O(1), offer and poll are O(log n), and its iteration order is not sorted.

Think of it like this

A hospital emergency room. Patients don't go in the order they arrived; the nurse always calls the most urgent one next. When a new patient arrives, the nurse only needs to know where they fit relative to the most urgent, not to keep the whole waiting room in perfect order. That's a priority queue, and keeping "just enough order" is exactly what makes it fast.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Priority queue: A queue that always gives you the most important element next, not the oldest.
Heap: A tree where every parent is ordered before its children, so the best element is always at the top.
Min-heap and max-heap: In a min-heap the smallest element is at the top; in a max-heap the largest is.
Complete binary tree: A tree where every level is full except possibly the last, which fills from the left. It fits perfectly into an array.
Sift up / sift down: Moving an element up or down the tree, swapping with parent or child, until the heap rule holds again.
Heapify: Turning an unordered array into a heap in one O(n) pass.
Top-k: Finding the k largest (or smallest) items in a big collection.

Step by step

01A tree stored in an array

The heap [1, 2, 5, 3, 7] is this tree: 1 at the root; its children 2 (index 1) and 5 (index 2); 2's children 3 (index 3) and 7 (index 4). Check the rule: every parent is ≤ its children. Notice that 5 sits above 3 even though 5 > 3: siblings and cousins are not ordered with each other.

The index arithmetic is what makes the array work: children of i are at 2i + 1 and 2i + 2, the parent of i is at (i - 1) >>> 1. A complete tree has no gaps, so no slots are wasted.

A tree stored in an arraydiagram

Rendering diagram…

02offer: add at the bottom, sift up

Offer 0 to [1, 2, 5, 3, 7]. It goes to index 5, whose parent is index 2 (value 5). 0 < 5, swap: now 0 is at index 2, parent index 0 (value 1). 0 < 1, swap: 0 is the root. Result [0, 2, 1, 3, 7, 5].

Each swap climbs one level, so the work is at most the tree's height, about log₂(n). For a million elements that's about 20 comparisons.

PriorityQueue.java (simplified from the JDK)whole filejava

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0) break;   // heap rule holds: stop
        es[k] = e;                              // move the parent down
        k = parent;
    }
    es[k] = key;
}

03poll: take the root, sift the last element down

poll() saves the root (the answer), takes the last element out of the array, puts it at index 0 and sifts it down: compare with the smaller of its two children, swap if it's bigger, repeat. Again at most log₂(n) levels.

Why move the last element? It keeps the tree complete (no hole in the middle of the array), so the index arithmetic stays valid.

poll: take the root, sift the last element downdiagram

Rendering diagram…

04Printing a PriorityQueue doesn't show priority order

System.out.println(pq) uses the iterator, which walks the array from index 0. You see heap order: the first element is the minimum, the rest only satisfy the parent ≤ child rule.

This surprises almost everyone the first time. To list elements in order without destroying the queue, copy it (new PriorityQueue<>(pq)) and poll the copy, or sort a list copy.

terminal

$ java Main

── expected output ──

[1, 2, 5, 3, 7]

05Ordering: natural, reversed or custom

Natural order needs Comparable elements (numbers, strings, your own classes implementing compareTo). For anything else pass a Comparator: new PriorityQueue<>(Comparator.comparingInt(Task::priority)).

A max-heap is new PriorityQueue<>(Comparator.reverseOrder()). Avoid the popular (a, b) -> b - a: subtraction overflows for large or negative values and silently breaks the heap. (a, b) -> Integer.compare(b, a) is always correct (Topic 9.10).

For deterministic order among ties, add a tie-breaker: .thenComparing(Task::name), or a sequence number for FIFO among equal priorities.

06Top-k with a heap of size k

To find the 3 largest of a million numbers, sorting costs O(n log n). Instead keep a min-heap of at most k elements: offer each number, and when the heap grows past k, poll the smallest. The heap always holds the k largest seen so far, and its root is the k-th largest.

Each step costs O(log k), so the total is O(n log k), and memory is O(k). That's why heaps appear in every "top 10 trending", "k closest" or "k most frequent" problem.

Try it yourself

1
Predict the heap array
In the mini heap, offer 0 after the five offers (before the polls). Predict the printed array before running: 0 lands at index 5, then climbs past 8 and 1.
2
FIFO among ties
Give Task a third component long seq and use .thenComparingLong(Task::seq) instead of thenComparing(Task::name). Offer the tasks with increasing sequence numbers and predict the order of the two priority-2 tasks now.
3
k smallest
Change topK to return the 3 smallest views. Which heap do you need now (a max-heap of size k), and what's the output? Predict [15, 45, 55] before running.

Code & diagrams

Heap order vs priority order New tab

Offering one by one and heapifying give different (both valid) heaps for the same numbers.

Expected output

printed (heap order): [1, 2, 5, 7, 3]
peek (the minimum):   1
polled one by one:    [1, 2, 3, 5, 7]
original untouched:   size 5
built by heapify:     [1, 2, 5, 3, 7]

Build a binary heap and watch sift up and sift down New tab

Expected output

offer 5 -> [5]
offer 3 -> [3, 5]
offer 8 -> [3, 5, 8]
offer 1 -> [1, 3, 8, 5]
offer 4 -> [1, 3, 8, 5, 4]
poll 1 -> [3, 4, 8, 5]
poll 3 -> [4, 5, 8]

Custom priorities, max-heaps and tie-breaking New tab

Without thenComparing, the two priority-2 tasks could come out in either order.

Expected output

1 fix outage
2 answer email
2 write report
3 book travel
max-heap polls: 9 7

Top-k largest with a size-k min-heap New tab

Expected output

top 3: [980, 760, 410]
top 1: [980]
4th largest is the root: 300

The (a, b) -> b - a overflow trap New tab

The subtraction overflows to -1, so the comparator lies about which number is bigger.

Expected output

b - a:           -2147483648 -3 2147483647 5
Integer.compare: 2147483647 5 -3 -2147483648
MAX_VALUE - MIN_VALUE = -1

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Queue elements with no ordering

Declare record Job(String name, int priority) { } and run Queue<Job> jobs = new PriorityQueue<>(); jobs.offer(new Job("backup", 2));.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.ClassCastException: class Job cannot be cast to class java.lang.Comparable (Job is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')

at java.base/java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:643)

at java.base/java.util.PriorityQueue.siftUp(PriorityQueue.java:639)

at java.base/java.util.PriorityQueue.offer(PriorityQueue.java:330)

at Main.main(Main.java:6)

Break #2

Expect the printout to be sorted

Build new PriorityQueue<>(List.of(7, 3, 5, 1, 2)) and print it, expecting [1, 2, 3, 5, 7].

terminal

$ java Main

── what you'll see ──

[1, 2, 5, 3, 7]

Myth vs fact

Myth

A PriorityQueue keeps its elements sorted.

Fact

It keeps them in heap order: each parent ≤ its children. Only the head is guaranteed; the full order appears only as you poll.

Myth

Equal-priority elements come out in the order they were added.

Fact

Heaps aren't stable. Add a sequence number to the comparator if you need FIFO among ties.

Myth

PriorityQueue.remove(x) is O(log n).

Fact

Finding x is a linear scan, O(n); only the repair after removal is O(log n). For frequent arbitrary removals use a TreeSet/TreeMap, or "lazy deletion" (mark and skip on poll).

Myth

(a, b) -> b - a is a fine max-heap comparator.

Fact

It overflows when the difference exceeds the int range. Use Comparator.reverseOrder() or Integer.compare(b, a).

Interview problem

The problem

Find the k-th largest element in a stream

Design a class KthLargest(int k, int[] initial) with int add(int val) that returns the k-th largest element of everything seen so far after adding val. Calls to add may number in the hundreds of thousands.

You're given

k ≥ 1; at least k - 1 elements exist before the first add.
add must be fast; memory must not grow with the stream.

The interviewer follows up

How would you get the running median instead?

What if values can also be removed from the stream?

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Heapify from a collection (PriorityQueue(Collection)) sifts down every non-leaf node from the last parent to the root. Most nodes are near the bottom and move only a little, so the total is O(n), not O(n log n).
▸
The array starts at 11 slots and grows by oldCapacity + 2 while under 64 and by 50% afterwards, like ArrayDeque. There's no trimToSize; a queue that once held millions keeps its big array.
▸
PriorityQueue doesn't support "decrease key" (changing an element's priority in place). Changing a field an element's comparator uses corrupts the heap silently. Dijkstra implementations in Java therefore push a new entry with the better distance and skip stale ones when polled (/dsa/shortest-path).
▸
For a sorted structure that supports removal and both ends, TreeMap/TreeSet is O(log n) for everything at about three times the memory per element. A heap is the right tool only when you just need repeated access to the minimum (or maximum).

Remember this

1
PriorityQueue<E> (Java 5) is a Queue whose poll() returns the smallest element according to natural ordering (Comparable) or a Comparator you pass in. With Comparator.reverseOrder() it returns the largest instead: a max-heap. Equal-priority elements come out in no guaranteed order; it isn't FIFO among ties.
2
Inside, it's a binary min-heap: a complete binary tree in which every parent is ≤ its children, so the minimum is always at the root. The tree lives in a plain array, Object[] queue, level by level: the root at index 0, and for a node at index i, its children at 2i + 1 and 2i + 2 and its parent at (i - 1) / 2. No node objects, no links, just arithmetic on indexes.
3
offer(e) puts the new element in the first free slot (the bottom of the tree) and sifts it up: while it's smaller than its parent, swap them. poll() removes the root, moves the last element into the root and sifts it down: while it's bigger than its smaller child, swap them. Both walk one root-to-leaf path, at most log₂(n) levels: O(log n). peek() just reads index 0: O(1).
4
Only the root is guaranteed to be the minimum. The rest of the array is in heap order, not sorted order, so toString(), for-each loops, stream() and toArray() show an order that looks random. To get elements in priority order, poll them one by one (that's heapsort, O(n log n)), or sort a copy.
5
Other costs: remove(Object) and contains are O(n) linear scans; building from a collection (new PriorityQueue<>(list)) uses heapify, which is O(n), cheaper than n separate offers. The default capacity is 11 and it grows automatically. null elements are rejected, and it isn't thread-safe (PriorityBlockingQueue is, Topic 13.8).
6
Heaps are the engine behind top-k problems (keep a min-heap of size k: O(n log k)), merging k sorted lists, scheduling the next event or job, Dijkstra's shortest paths, and the running median (two heaps). The DSA course's Heaps module (/dsa/heaps) works through all of these.

Explain it without notes

How is PriorityQueue implemented, and what are the costs of offer, poll, peek, remove(Object) and contains?

Why doesn't printing a PriorityQueue show sorted order?

How do you find the k largest elements of a large array efficiently, and what is the complexity?

How do you make a max-heap in Java, and what's wrong with (a, b) -> b - a?

Practice

Merge the sorted arrays {1, 4, 7}, {2, 5, 8} and {3, 6, 9} into one sorted list using a PriorityQueue<int[]> holding {value, arrayIndex, elementIndex}.

Return the 2 most frequent words in ["tea", "cake", "tea", "chai", "cake", "tea"], using a HashMap for counts and a PriorityQueue for the top 2.

Simulate a meeting-room scheduler: given meetings {0, 30}, {5, 10} and {15, 20} (start, end), compute the minimum number of rooms needed using a min-heap of end times.

Trade-offs

↔
A heap gives O(1) access to the minimum and O(log n) updates with a compact array, but no fast search, no fast arbitrary removal and no sorted iteration. A TreeSet gives all of those at higher memory and constant-factor cost.
↔
Top-k with a size-k heap is O(n log k) and streams; sorting is O(n log n) but simpler and gives the full order. For small inputs, sorting is often clearer and fast enough.
↔
Breaking ties with extra comparator fields makes output deterministic and testable, at the cost of a slightly slower comparison.

Done when you can

Done when you can draw a heap as a tree and as an array, with the index formulas.
Done when you can trace sift up and sift down by hand.
Done when you can give the cost of every PriorityQueue operation, including remove(Object).
Done when you know why printing a heap isn't sorted.
Done when you can build min-heaps, max-heaps and custom-priority heaps without overflow bugs.
Done when you can solve top-k and k-way merge with a heap.

Command Palette

Words you'll meet

Step by step

01A tree stored in an array

02offer: add at the bottom, sift up

03poll: take the root, sift the last element down

04Printing a PriorityQueue doesn't show priority order

05Ordering: natural, reversed or custom

06Top-k with a heap of size k

Try it yourself

Predict the heap array

FIFO among ties

k smallest

Code & diagrams

Break it on purpose

Queue elements with no ordering

Expect the printout to be sorted

Myth vs fact

Interview problem

Find the k-th largest element in a stream

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can