A retry queue holds jobs by due time. Every arrival you sort the list. Every tick you take index 0. With a few dozen jobs it looks fine. With tens of thousands it is a tax on every insert: you reordered everything to learn who is next.
A heap keeps the next-best element at the root without sorting the rest. Insert and extract are O(log n). Peek is O(1). The rest of the array is unordered on purpose.
ADT vs implementation, Big-O, and amortized live on the Data Structures Roadmap. This post stays on one layout: the binary heap, and the priority-queue contract it usually implements.
Why sorting the list is the wrong bill
The naive scheduler is honest about the API and expensive about the layout:
void enqueue(List<Job> pending, Job incoming) {
pending.add(incoming);
pending.sort(Comparator.comparing(Job::dueAt));
}
Job next(List<Job> pending) {
return pending.remove(0);
}sort is O(n log n) so that remove(0) can be “the earliest due.” You paid a full sort for a question that only needs the minimum. A heap answers that question at the root and leaves the other jobs unsorted.
| Job | Cheap layout | Expensive layout |
|---|---|---|
| Next-best item (scheduler, leaderboard eviction) | Heap / PriorityQueue | Sort the whole collection on every insert |
| Sorted scan of every key | TreeMap / sort once | Polling a heap just to print in order |
Two rules: heap-order and complete shape
A binary heap is a binary tree with two invariants. Break either one and the array tricks below stop working.
Complete shape. Fill level by level, left to right. The last level may be short, but there are no holes. That is why a heap fits in a compact array: index i has a parent and children you can compute, with no null pointers in the middle.
Heap-order. For a min-heap, every parent is less than or equal to its children. For a max-heap, every parent is greater than or equal to its children. Only the root is guaranteed to be the extreme. A left-to-right walk of the array is not sorted.
Min-heap (values). Complete, parent <= children. Not a BST.
1
/ \
3 8
/
5
Array: [1, 3, 8, 5]A BST would put smaller keys left and larger keys right. A heap does not. 8 can sit left of nothing interesting; it only has to be at least as large as its parent. That is the whole trade: you give up sorted order to keep the extreme at the root in logarithmic time.
The tree lives in an array
Index 0 is the root. Parent and children are arithmetic — 0-based, the same convention PriorityQueue uses:
parent(i) = (i - 1) / 2
leftChild(i) = 2 * i + 1
rightChild(i) = 2 * i + 2For [1, 3, 8, 5]:
i=0 value 1 left=1 (3) right=2 (8)
i=1 value 3 left=3 (5) right=4 (none)
i=2 value 8 no children in a four-element heap
i=3 value 5 parent=1No node objects. No left/right fields. Growth is the same amortized doubling as a dynamic array — the hub’s amortized note applies to the backing store, not to sift itself. Sift is worst-case O(log n) because the tree height of a complete binary tree is floor(log2 n).
Sift up on insert, sift down on extract
Insert appends at the next free slot (the end of the array), then restores heap-order by walking toward the root. Extract takes the root, moves the last element into index 0, and restores heap-order by walking toward the leaves.
Sift up (after insert): while the node is out of order with its parent, swap and continue. At most one swap per level.
void siftUp(int[] a, int i, Comparator<Integer> cmp) {
while (i > 0) {
int p = (i - 1) / 2;
if (cmp.compare(a[i], a[p]) >= 0) {
break;
}
int tmp = a[i];
a[i] = a[p];
a[p] = tmp;
i = p;
}
}Insert 1 into [3, 5, 8]:
append: [3, 5, 8, 1]
sift up: 1 vs parent 5 -> swap -> [3, 1, 8, 5]
1 vs parent 3 -> swap -> [1, 3, 8, 5]Sift down (after extract): while the node is out of order with the better child, swap with that child and continue.
void siftDown(int[] a, int size, int i, Comparator<Integer> cmp) {
while (true) {
int left = 2 * i + 1;
if (left >= size) {
break;
}
int best = left;
int right = left + 1;
if (right < size && cmp.compare(a[right], a[left]) < 0) {
best = right;
}
if (cmp.compare(a[best], a[i]) >= 0) {
break;
}
int tmp = a[i];
a[i] = a[best];
a[best] = tmp;
i = best;
}
}Poll 1 from [1, 3, 8, 5]:
move last to root: [5, 3, 8]
sift down: 5 vs better child 3 -> swap -> [3, 5, 8]Peek is a read of index 0. No sift. That is why “who is next?” is O(1) once the heap is honest.
Building a heap from n unordered items by inserting one-by-one is O(n log n). Heapify (sift down from the last parent to the root) is O(n). You rarely write heapify yourself in Java — PriorityQueue has a collection constructor that does it — but the cheat sheet lists it so “n offers at startup” does not surprise you.
Min-heap: smallest at the root
A min-heap is the default mental model and the JDK default. Compare so that the smaller parent wins. Peek and poll return the minimum.
PriorityQueue<Integer> due = new PriorityQueue<>();
due.offer(30);
due.offer(10);
due.offer(20);
due.peek(); // 10
due.poll(); // 10
due.peek(); // 20Use a min-heap when the hot operation is “give me the soonest / cheapest / lowest-score item”: delayed jobs, Dijkstra-style “next vertex by distance,” a timer wheel’s next expiry. Natural ordering on Integer, Instant, or a Comparator.comparing(...) that points at the field you want small.
Max-heap: same tree, inverted compare
A max-heap is the same complete array and the same sift. The only change is the comparison: the larger parent wins. Peek and poll return the maximum.
PriorityQueue<Integer> highScores = new PriorityQueue<>(Comparator.reverseOrder());
highScores.offer(30);
highScores.offer(10);
highScores.offer(20);
highScores.peek(); // 30Same structure, inverted compare. A custom Comparator that orders Job by remaining retries descending is still a max-heap on that key. You do not need a second data type.
Note: new PriorityQueue<>() with no comparator is a min-heap for types that implement Comparable. Forcing a max-heap is Comparator.reverseOrder() or comparing(...).reversed(), not a different class.
Typical max-heap jobs: “evict the largest,” a bounded buffer of top-k scores (store the k best in a min-heap of size k — the root is the weakest of the winners), or a scheduler that always runs the highest-priority ready task.
Priority queue is the contract; heap is a layout
From the hub: an ADT is the contract; an implementation is the layout. A priority queue is the contract: insert an item with a priority, peek the next-best, extract the next-best. It is not FIFO. Equal priorities have no promised order unless you add a tie-breaker (sequence number, insertion counter).
A binary heap is one layout that delivers that contract. Others exist (unsorted array: insert O(1), extract O(n); sorted array: insert O(n), extract O(1)). The binary heap is the usual production default because both mutating operations stay O(log n) and the representation is an array you already understand.
ADT: priority queue — next-best in, next-best out
Implementation: binary heap — complete tree in an array
Not a queue: FIFO is ArrayDeque, not PriorityQueue
Not a sort: iterating the heap is not sorted orderReach for the ADT name in design talk and the heap name when you mean the array + sift layout. Confusing the two is how people expect PriorityQueue.iterator() to walk from min to max.
PriorityQueue in the JDK
java.util.PriorityQueue is an unbounded binary heap. Default comparator is natural order — a min-heap. It is not thread-safe; concurrent producers use PriorityBlockingQueue or an external lock.
record Job(String id, Instant dueAt) {}
PriorityQueue<Job> pending = new PriorityQueue<>(Comparator.comparing(Job::dueAt));
pending.offer(new Job("retry-42", Instant.now().plusSeconds(30)));
pending.offer(new Job("retry-7", Instant.now().plusSeconds(5)));
Job next = pending.poll(); // retry-7Operations you will actually call:
| Method | Heap job | Cost |
|---|---|---|
offer / add | append + sift up | O(log n) |
peek | read root | O(1) |
poll | take root, sift down | O(log n) |
remove(Object) / contains | scan, then maybe sift | O(n) |
Note: iterator() and toArray() do not yield priority order. Drain with poll() if you need items from best to worst — that is heapsort, O(n log n), and it empties the queue. For a snapshot that must stay sorted while you still mutate, you wanted a TreeMap / TreeSet, not a heap.
null is forbidden. Duplicate values are allowed. Stability among equal priorities is not part of the contract — add a monotonic seq field to the comparator if “same due time, older job first” matters.
Fibonacci heap: a name you will hear
Textbooks (and interview prompts about Dijkstra) mention the Fibonacci heap because decrease-key is amortized O(1) and extract-min is amortized O(log n). That bound is why the name appears in algorithm analysis.
You will almost never implement one. The constants are large, the structure is a forest of trees with parent pointers and mark bits, and the JDK does not ship a Fibonacci heap. Production Java that needs “next-best” uses PriorityQueue. If an algorithm needs decrease-key as the hot path, the usual move is a handle map plus a binary heap, a pairing heap in a library, or a different algorithm — not a from-scratch Fibonacci heap on a Friday afternoon.
Treat the name as literacy: you can recognize it in a complexity table without building one.
When not to use a heap
Skip the heap when the hot operation is not “next-best”:
- You need sorted iteration, not one extreme. Sort a copy, or keep a
TreeMap/TreeSet. Polling a heap to print in order is a slow way to sort, and it destroys the queue. - Arbitrary decrease-key is frequent. Finding an element in a binary heap is
O(n)unless you store its index yourself. Dijkstra-style “this vertex got cheaper” is the classic mismatch; a textbook Fibonacci heap exists for that sentence, not as your default collection. - You needed FIFO. Same priority, arrival order: that is a queue (
ArrayDeque), or a priority queue with an explicit tie-breaker.PriorityQueuewill not preserve insertion order among equals. nis tiny and the list is already there. Sorting twenty jobs is simpler than explaining a heap. Measure when the collection grows; do not invent a heap for a UI dropdown.
Search-by-id, range queries, and “give me everything between A and B” are other layouts. A heap answers one question well: what is next, cheaply, as the set mutates.
Cheat sheet
Heap: complete binary tree in an array; extreme at index 0
Heap-order: parent <= children (min) or parent >= children (max)
Index: parent (i-1)/2; left 2i+1; right 2i+2
Insert: append + sift up O(log n)
Extract: root out, last to 0, sift down O(log n)
Peek: a[0] O(1)
Build: heapify O(n)
ADT: priority queue (next-best); heap is a layout
JDK: PriorityQueue — min-heap by default
Max-heap: Comparator.reverseOrder() — same class
Iterator: not sorted
Fibonacci: a name in decrease-key analysis; do not implement
Avoid: sorted scans (TreeMap); FIFO (ArrayDeque); frequent decrease-keyDo:
- Name the hot operation: next-best as the set grows. That is a heap.
- Use
PriorityQueuewith aComparatoron the field you care about. - Add a sequence number when equal priorities must stay stable.
Don’t:
- Sort the whole list on every insert to keep index
0honest. - Expect
iterator()to walk from min to max. - Reach for a Fibonacci heap because a textbook mentioned decrease-key.
Wrap-up
A binary heap is a complete tree stored in an array. Heap-order keeps the next-best element at the root; complete shape makes parent and children a pair of index formulas. Sift up after insert, sift down after extract, both O(log n). Min and max are the same layout with the comparison flipped.
The ADT is a priority queue. The JDK type is PriorityQueue, a min-heap unless you pass a reversed comparator. Fibonacci heap is a name you will see when decrease-key is the theoretical bottleneck — not a type you should build for production Java.
If the hot path is “who is next?” as items arrive and leave, a heap is the layout that makes that cheap. If the hot path is “walk everything in order” or “make this specific item cheaper,” pick a sorted map or a different algorithm. The series hub is the glossary and index when you need to match a different job to a different layout.