JAVA-201 · Lesson 11 of 12 · 23 min
Priority queues and heaps
▶ Video coming soon A video version of this lesson is on the way.
Tamsin's repair rack from lesson 4 was a plain queue, first come, first served. Real repair nights are not quite like that. A commuter with a flat tire who needs the bike tomorrow morning should go ahead of a full tune-up that can wait until next week, and Odile's rental bikes, which earn money, should go ahead of both when they come back damaged. Within each level of urgency, arrival order still decides. The plan for Friday, April 9, 2027, the last regular session of the term, is the structure built for exactly this: the priority queue, and the heap that makes it fast.
A queue ordered by priority
A priority queue always hands out its smallest element first, according to the elements' natural order or a comparator, no matter when it was added. Java's PriorityQueue implements the Queue interface, so it has the familiar offer, poll and peek. offer and poll are O(log n) and peek is O(1). Unlike a TreeSet, it allows duplicates, and it never sorts all its elements; it only keeps the smallest one ready at the front.
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> lowStock = new PriorityQueue<>();
for (int count : new int[] {14, 3, 22, 6, 3, 9}) lowStock.offer(count);
System.out.println("smallest count: " + lowStock.peek());
StringBuilder order = new StringBuilder();
while (!lowStock.isEmpty()) order.append(lowStock.poll()).append(' ');
System.out.println("polled in order: " + order.toString().trim());
}
}smallest count: 3 polled in order: 3 3 6 9 14 22
What this code does
The counts are offered in no particular order, but peek shows the smallest, 3, at once. Each poll removes the current smallest, so polling until the queue is empty gives the counts in ascending order, with both 3s kept. Integers use their natural order, so no comparator is needed.
For anything other than natural order, give the constructor a Comparator, built as in lesson 7. To make the queue hand out the largest first, use Comparator.reverseOrder(). For Tamsin's rack, the order is urgency first and then arrival number, and both levels are easy to express with comparingInt and thenComparingInt.
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
enum Urgency { RENTAL_DAMAGE, NEEDED_TOMORROW, ROUTINE }
record Job(int arrival, String owner, Urgency urgency) {}
public static void main(String[] args) {
Comparator<Job> order = Comparator.comparing(Job::urgency).thenComparingInt(Job::arrival);
PriorityQueue<Job> rack = new PriorityQueue<>(order);
rack.offer(new Job(1, "Mei Lin, tune-up", Urgency.ROUTINE));
rack.offer(new Job(2, "Ana Ruiz, flat tire", Urgency.NEEDED_TOMORROW));
rack.offer(new Job(3, "rental City 2, bent wheel", Urgency.RENTAL_DAMAGE));
rack.offer(new Job(4, "Theo Park, brake cable", Urgency.NEEDED_TOMORROW));
rack.offer(new Job(5, "Ravi Shah, gears", Urgency.ROUTINE));
while (!rack.isEmpty()) {
Job j = rack.poll();
System.out.println(j.urgency() + " #" + j.arrival() + " " + j.owner());
}
}
}RENTAL_DAMAGE #3 rental City 2, bent wheel NEEDED_TOMORROW #2 Ana Ruiz, flat tire NEEDED_TOMORROW #4 Theo Park, brake cable ROUTINE #1 Mei Lin, tune-up ROUTINE #5 Ravi Shah, gears
What this code does
Enums compare in the order their constants are declared, so RENTAL_DAMAGE comes before NEEDED_TOMORROW and ROUTINE. The comparator sorts by urgency and then by arrival number, so the damaged rental goes first, then Ana before Theo, and Mei before Ravi. Each poll hands out the most urgent job that has waited longest.
A PriorityQueue is not sorted
Printing a PriorityQueue, or looping over it with for-each, does not show its elements in priority order. The iterator walks the internal array in whatever order the heap happens to keep it, which only guarantees that the smallest element is first. If you need every element in order, poll them one by one, or copy them into a list and sort it.
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(14, 3, 22, 6, 9));
System.out.println("toString, the heap's array order: " + pq);
List<Integer> sorted = new ArrayList<>(pq);
Collections.sort(sorted);
System.out.println("sorted copy: " + sorted);
System.out.println("head is still the smallest: " + pq.peek());
}
}toString, the heap's array order: [3, 6, 22, 14, 9] sorted copy: [3, 6, 9, 14, 22] head is still the smallest: 3
What this code does
toString shows the elements in the order of the heap's internal array, which is what this JDK printed; only the first position, 3, is guaranteed. Copying into a list and sorting it gives the true ascending order. The queue itself is unchanged, and peek still returns the smallest element.
The binary heap
A PriorityQueue is built on a binary heap: a binary tree that is complete, meaning every level is full except possibly the last, which fills from the left, and that obeys the heap property: every node is smaller than or equal to its children. So the smallest element is always at the root. Unlike a binary search tree, a heap says nothing about left versus right; it only orders parents above children, which is less work to maintain.
The trick that makes a heap efficient is that a complete tree fits perfectly in an array, with no node objects at all. The root is at index 0, and for the node at index i, its children are at 2i + 1 and 2i + 2 and its parent is at (i − 1) / 2, using integer division. Moving around the tree is just arithmetic on indexes.
Adding and removing: sift up and sift down
To add an element, put it in the next free slot at the end of the array, which keeps the tree complete, and then sift it up: while it is smaller than its parent, swap the two. To remove the smallest, take the root, move the last element into its place, and sift it down: while it is larger than its smaller child, swap with that child. Each sift moves along one path from root to leaf, so both operations are O(log n).
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
MinHeap h = new MinHeap(16);
for (int x : new int[] {14, 3, 22, 6, 9}) {
h.add(x);
System.out.println("add " + x + " -> " + h);
}
System.out.println("poll " + h.poll() + " -> " + h);
System.out.println("poll " + h.poll() + " -> " + h);
System.out.println("swaps so far: " + h.swaps);
}
}
class MinHeap {
private final int[] a;
private int size;
int swaps;
MinHeap(int capacity) { a = new int[capacity]; }
void add(int x) {
a[size] = x;
int i = size++;
while (i > 0 && a[i] < a[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
int poll() {
int top = a[0];
a[0] = a[--size];
int i = 0;
while (true) {
int l = 2 * i + 1, r = l + 1, small = i;
if (l < size && a[l] < a[small]) small = l;
if (r < size && a[r] < a[small]) small = r;
if (small == i) return top;
swap(i, small);
i = small;
}
}
private void swap(int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
swaps++;
}
@Override
public String toString() { return Arrays.toString(Arrays.copyOf(a, size)); }
}add 14 -> [14] add 3 -> [3, 14] add 22 -> [3, 14, 22] add 6 -> [3, 6, 22, 14] add 9 -> [3, 6, 22, 14, 9] poll 3 -> [6, 9, 22, 14] poll 6 -> [9, 14, 22] swaps so far: 4
What this code does
Each add puts the new value at the end and swaps it up past any larger parent, so 3 rises to the root as soon as it arrives. poll takes the root, moves the last element to the top and swaps it down past its smaller child until the heap property holds again. After every step the smallest value is at index 0, and the whole job took only a handful of swaps.
| Operation | Binary heap | Sorted array | Unsorted list |
|---|---|---|---|
| Look at the smallest (peek) | O(1) | O(1) | O(n) |
| Add (offer) | O(log n) | O(n), to keep it sorted | O(1) |
| Remove the smallest (poll) | O(log n) | O(n) at the front, or O(1) at the back | O(n) |
| Build from n elements | O(n) with heapify | O(n log n) to sort | O(n) |
| Remove an arbitrary element | O(n) to find it | O(n) | O(n) |
Building a heap in O(n)
Adding n elements one at a time costs O(n log n). There is a faster way to turn a whole array into a heap at once, called heapify: sift down every node that has children, starting from the last such node and working back to the root. Most nodes are near the bottom and only move a short distance, and the total work comes out to O(n). The PriorityQueue constructor that takes a collection uses this.
public class Main {
public static void main(String[] args) {
int n = 612;
int[] counts = new int[n];
for (int i = 0; i < n; i++) counts[i] = (i * 37) % 101;
int[] a = counts.clone();
int heapifySwaps = 0;
for (int i = n / 2 - 1; i >= 0; i--) heapifySwaps += siftDown(a, i, n);
int[] b = new int[n];
int addSwaps = 0;
for (int size = 0; size < n; size++) {
b[size] = counts[size];
int i = size;
while (i > 0 && b[i] < b[(i - 1) / 2]) {
int t = b[i]; b[i] = b[(i - 1) / 2]; b[(i - 1) / 2] = t;
i = (i - 1) / 2;
addSwaps++;
}
}
System.out.println("smallest " + a[0] + " and " + b[0]);
System.out.println("swaps with heapify: " + heapifySwaps + ", adding one at a time: " + addSwaps);
}
static int siftDown(int[] a, int i, int size) {
int swaps = 0;
while (true) {
int l = 2 * i + 1, r = l + 1, small = i;
if (l < size && a[l] < a[small]) small = l;
if (r < size && a[r] < a[small]) small = r;
if (small == i) return swaps;
int t = a[i]; a[i] = a[small]; a[small] = t;
i = small;
swaps++;
}
}
}smallest 0 and 0 swaps with heapify: 461, adding one at a time: 674
What this code does
Both methods build a valid heap of 612 counts with the smallest value, 0, at the root. Heapify sifts down from the last parent towards the root, and it needs fewer swaps than adding the elements one at a time. The counts are made by a fixed formula rather than a random generator, so the result is the same every run.
Heaps also give a sorting algorithm, heapsort: heapify the array, then repeatedly swap the root to the end and sift down the rest. It is O(n log n) in the worst case and needs no extra memory, but it is not stable and is usually slower in practice than TimSort, which is why Java does not use it for List.sort.
Top k: a small heap for a big list
A common question is "which k items are largest?": Kofi wants the five parts used most this year out of 612. Sorting all 612 is O(n log n). A neater method keeps a min-heap of size k: for each item, add it, and if the heap now has more than k items, poll the smallest. The heap always holds the k largest seen so far, and the total cost is O(n log k), which for k = 5 is close to linear.
import java.util.*;
public class Main {
record Usage(String code, int used) {}
public static void main(String[] args) {
List<Usage> year = List.of(new Usage("TUBE-700x25", 212), new Usage("PAD-ROAD", 88),
new Usage("CABLE-BRAKE", 64), new Usage("BELL", 12), new Usage("CHAIN-11", 47),
new Usage("TUBE-26x2.1", 130), new Usage("GRIPS", 30), new Usage("PAD-DISC", 71));
int k = 3;
PriorityQueue<Usage> top = new PriorityQueue<>(Comparator.comparingInt(Usage::used));
for (Usage u : year) {
top.offer(u);
if (top.size() > k) top.poll();
}
List<Usage> best = new ArrayList<>(top);
best.sort(Comparator.comparingInt(Usage::used).reversed());
for (Usage u : best) System.out.println(u.code() + " used " + u.used());
}
}TUBE-700x25 used 212 TUBE-26x2.1 used 130 PAD-ROAD used 88
What this code does
The heap is ordered by usage, smallest first, and is never allowed to hold more than three items, so each extra item pushes out the least used one. After the loop it holds the three most used parts, which are then sorted for printing, most used first. Only a heap of three was ever kept, however long the list.
Priority queues in practice
Priority queues turn up wherever something must always process the most important item next: scheduling repair jobs or computer tasks, simulations that handle events in time order, merging several sorted lists, and graph algorithms such as Dijkstra's shortest paths, which JAVA-205 covers. Two practical limits are worth knowing. Removing an arbitrary element, or changing an element's priority, is O(n), because the heap must find it first; if priorities change often, remove the element and add it again. And PriorityQueue is not safe for use by several threads; java.util.concurrent offers PriorityBlockingQueue for that.
import java.util.PriorityQueue;
public class Main {
record Bike(String tag) {}
public static void main(String[] args) {
PriorityQueue<Bike> q = new PriorityQueue<>();
q.offer(new Bike("SG-0007-AR"));
System.out.println("one bike queued");
q.offer(new Bike("SG-0003-CI"));
}
}What this code does
Bike has no natural order and the queue was given no comparator, so the second offer cannot compare the two bikes and throws ClassCastException. The first offer succeeds because a heap of one needs no comparison. Give the queue a comparator such as Comparator.comparing(Bike::tag).
$ javac Main.java
$ java Main
Exception in thread "main" java.lang.ClassCastException: class Main$Bike cannot be cast to class java.lang.Comparable (Main$Bike 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:8)Try it yourself
Largest first
Make the priority queue hand out the largest count first by passing Comparator.reverseOrder() to its constructor.
The program should print 22 14 9 6 3.
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int c : new int[] {14, 3, 22, 6, 9}) pq.offer(c);
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) sb.append(pq.poll()).append(' ');
System.out.println(sb.toString().trim());
}
}Try it yourself
The heap arithmetic
Complete parent, left and right with the array formulas for a binary heap: the parent of i is (i - 1) / 2, and the children are 2 * i + 1 and 2 * i + 2. The program then checks the heap property for the array.
The program should print parent of 4 is 1, children of 1 are 3 and 4 and heap property holds: true.
public class Main {
public static void main(String[] args) {
int[] heap = {3, 6, 9, 14, 22, 11};
System.out.println("parent of 4 is " + parent(4) + ", children of 1 are " + left(1) + " and " + right(1));
boolean ok = true;
for (int i = 1; i < heap.length; i++) if (heap[parent(i)] > heap[i]) ok = false;
System.out.println("heap property holds: " + ok);
}
static int parent(int i) { return 0; }
static int left(int i) { return 0; }
static int right(int i) { return 0; }
}Common mistakes
MistakePrinting a PriorityQueue and expecting sorted order.
InsteadOnly the head is guaranteed; poll repeatedly or copy and sort to see everything in order.
MistakeUsing a TreeSet as a priority queue when items can tie.
InsteadA TreeSet drops elements that compare as equal; PriorityQueue keeps duplicates.
MistakeForgetting that PriorityQueue gives the smallest first.
InsteadPass Comparator.reverseOrder() or a reversed comparator to get the largest first.
MistakeSorting a whole list to find the top few items.
InsteadKeep a min-heap of size k, which costs O(n log k).
MistakeChanging a field that the comparator uses while the element is in the queue.
InsteadRemove the element, change it, and add it again, so the heap can reposition it.
Summary and key terms
- A priority queue always hands out its smallest element first, by natural order or a comparator, and Java's PriorityQueue offers it with offer and poll in O(log n) and peek in O(1).
- A comparator gives any order, such as urgency and then arrival, and Comparator.reverseOrder gives largest first.
- A PriorityQueue is not sorted: its iterator and toString follow the heap's array, and only the head is guaranteed.
- It is built on a binary heap, a complete binary tree in which every parent is no larger than its children, stored in an array where the children of i are at 2i + 1 and 2i + 2 and its parent at (i − 1) / 2.
- Adding sifts the new element up and removing the smallest sifts the last element down, each along one path.
- Heapify builds a heap from an array in O(n), heapsort sorts in O(n log n) without extra memory, and a min-heap of size k finds the top k items in O(n log k).
- Elements with no order cause ClassCastException.
- Priority queue
- A queue that always hands out its smallest element according to an order.
- PriorityQueue
- Java's priority queue class, built on a binary heap.
- Binary heap
- A complete binary tree in which each parent is no larger than its children.
- Heap property
- The rule that every node is smaller than or equal to its children in a min-heap.
- Complete binary tree
- A binary tree whose levels are all full except perhaps the last, which fills from the left.
- Min-heap and max-heap
- Heaps with the smallest, or the largest, element at the root.
- Sift up
- Swapping a new element with its parent until the heap property holds.
- Sift down
- Swapping an element with its smaller child until the heap property holds.
- Heapify
- Turning an array into a heap in O(n) by sifting down from the last parent.
- Heapsort
- A sorting algorithm that heapifies and then repeatedly removes the root.
- Top k
- Finding the k largest or smallest items, often with a heap of size k.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Which element does PriorityQueue.poll() return?
Show answer
The smallest according to the queue's order.
Does printing a PriorityQueue show its elements in order?
Show answer
No; only the head is guaranteed to be the smallest.
Where are the children of the node at index 3 in a heap array?
Show answer
At indexes 7 and 8.
Why are offer and poll O(log n)?
Show answer
Each sifts one element along a single path whose length is the height of the tree.
How can you find the 5 most used parts without sorting all 612?
Show answer
Keep a min-heap of size 5 and poll whenever it grows past 5.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.