How does Java's PriorityQueue work inside: its heap array, sifting on offer and poll, array growth, and bulk-constructor heapify?
answer
- one array, read as a tree
- children at 2n+1 and 2n+2
- new element climbs from the end
- last element refills the root
- Floyd: last non-leaf back to root
basics
~20 sPriorityQueue keeps a binary min-heap in an Object array: offer sifts the new element up from the end, poll sifts the last element down from the root. The array grows by copying, and building from an unordered collection runs O(n) heapify.
solid answer
~50 s`PriorityQueue` holds a balanced binary heap in a package-private `Object[] queue`: the children of `queue[n]` are `queue[2*n+1]` and `queue[2*(n+1)]`, and `queue[0]` is the least element under the comparator or natural ordering. `offer` grows the array if it is full, then sifts up from slot `size`, moving larger parents down until the new element fits. `poll` takes `queue[0]`, pulls the last element out of the array and sifts it down from the root, promoting the smaller child at each level. At JDK 27, as at 25, growth copies to `2n + 2` slots below length 64 and to `1.5n` from there, and nothing shrinks the array. `new PriorityQueue<>(collection)` copies the elements and runs Floyd's O(n) `heapify`, from the last non-leaf back to the root, unless the source is a `SortedSet` or a plain `PriorityQueue`, whose order it keeps.
code
java · 18 linesimport java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class HeapLayout {
public static void main(String[] args) {
// A plain List takes the heapify path. toArray() happens to expose the heap array;
// its Javadoc promises no order, so print it here and never depend on it.
var pq = new PriorityQueue<Integer>(List.of(9, 7, 5, 3, 1));
System.out.println("heapify " + Arrays.toString(pq.toArray()));
pq.offer(2); // starts in slot 5, parent 5 moves down, stops under 1
System.out.println("offer 2 " + Arrays.toString(pq.toArray()));
System.out.println("poll -> " + pq.poll()); // 5 leaves the last slot and sifts from the root
System.out.println("after " + Arrays.toString(pq.toArray()));
}
}go deeper
Recall that a PriorityQueue is one array treated as a tree, with the least element at index 0. New elements start at the end and climb; poll takes the root and lets the last element find a new place.
Explain the index arithmetic, the sift up on offer, the sift down on poll with its smaller-child choice, and the growth rule. Say which constructors heapify and why that build is linear rather than n log n.
Show the production consequences: presize a queue whose size you can estimate, remember the array never shrinks after a burst, and prefer a constructor for bulk loads under natural ordering, because addAll sifts one element at a time.
Weigh what the heap gives up: cheap head access comes with linear search and removal and arbitrary ties. Decide when a team should add a sequence tie-breaker or move to an ordered set, rather than tuning capacity numbers the Javadoc does not promise.
## The structure: a tree stored in an array A **binary heap** is a complete binary tree in which every node is less than or equal to each of its descendants. "Less" is decided by the queue's `Comparator`, or by the elements' natural ordering when there is none. "Complete" means every level is full except perhaps the last, which fills from the left, so the tree fits a gapless array with no node objects. `java.util.PriorityQueue` stores it that way: | Member | Declared as | Role | |---|---|---| | `queue` | package-private `transient Object[]` | the heap, level by level | | `size` | package-private `int` | how many leading slots are in use | | `comparator` | `private final` | `null` means natural ordering | | `DEFAULT_INITIAL_CAPACITY` | `private static final int`, value 11 | array length from the no-arg constructor | Positions follow from the index alone: - **Children** of `queue[n]` are `queue[2*n+1]` and `queue[2*(n+1)]`. - **Parent** of slot `k` is `(k - 1) >>> 1`. - **Leaves** start at slot `size >>> 1`, so only the slots before it can sift down. The rule says nothing about siblings, so `queue[0]` is always least while the rest is only partly ordered, and walking the array is not guaranteed to give sorted output. ## offer: sift up 1. `offer` rejects `null` with a `NullPointerException` and increments `modCount`. (`add` just calls `offer`.) 2. If `size` has reached `queue.length`, the private `grow` replaces the array. 3. Slot `size` becomes a hole. While the hole is not the root, its parent moves down into it, unless the new element is greater than or equal to that parent, which stops the loop. 4. The element is written into the hole and `size` goes up by one. ```java // java.util.PriorityQueue, private siftUpComparable, the loop while (k > 0) { int parent = (k - 1) >>> 1; Object e = es[parent]; if (key.compareTo((T) e) >= 0) break; es[k] = e; k = parent; } es[k] = key; ``` - **No swaps.** Parents move and the new element is written once, at the end. - **The cost is the climb.** One comparison per level, so at most the tree's height, and a new largest element stops after one. - **Natural ordering casts first**, so a non-`Comparable` element throws `ClassCastException` even on the first `offer`. `siftUpUsingComparator` is the comparator twin. ## poll: sift down 1. `poll` reads `queue[0]` and returns null if that slot is null, without consulting `size`. A stored null would look the same, the reason `Queue`'s Javadoc gives against inserting null. 2. `size` drops by one, the element in the last used slot is taken out as `x`, and that slot is nulled. 3. If elements remain, `x` sifts down from slot 0. While the hole has a child, the smaller child is chosen (the left, unless it compares greater than an existing right). If `x` is less than or equal to that child the loop stops; otherwise the child moves up and the hole moves down. 4. `x` is written into the hole and the old head is returned. Only the last slot can be vacated without leaving a gap, so its element is the one re-placed: - **Up to two comparisons per level**: one between the children, one against `x`. - **Ties are not first-in, first-out.** `x` re-enters at the root, so it can land above equal elements offered earlier, and the class Javadoc says "ties are broken arbitrarily". On JDK 27, seven equal-priority items offered as `a` to `g` poll as `a g f e d c b`. ## Growth The private `grow` calls `ArraysSupport.newLength` with the needed slot as its minimum growth and `oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1` as its preferred growth. Its source comment reads "Double size if small; else grow by 50%". - **Lengths** from the default run 11, 24, 50, 102, 153, 229 on JDK 27. - **A bulk-built queue starts full.** Its array is exactly as long as its contents, so the next `offer` grows it: 4 becomes 10. An empty source gets one slot. - **Nothing shrinks it.** Neither `poll` nor `clear` replaces the array, so a drained queue keeps its length while the elements become collectible. - **Presizing** with `PriorityQueue(int)` avoids the copies; a capacity below 1 throws `IllegalArgumentException`. - **Not a contract.** The class Javadoc says "The details of the growth policy are not specified". These numbers describe JDK 27; `PriorityQueue.java` is identical at JDK 25. ## Bulk construction and heapify `PriorityQueue(Collection)` checks the argument's runtime type, and the `SortedSet` and `PriorityQueue` overloads behave the same way: | Source | Comparator used | Heapify? | |---|---|---| | `SortedSet` | the set's | no: ascending order is already a valid heap | | exactly `PriorityQueue` | the source's | no: its array is copied as it stands | | a subclass of `PriorityQueue` | the source's | yes | | anything else | none, natural ordering | yes | The private `heapify` works from the bottom. Its index starts at `(n >>> 1) - 1`, the last non-leaf, and counts down to 0, sifting each slot down. About half the slots are leaves and start no sift, about a quarter can sift down at most one level, about an eighth at most two, so total work is proportional to n. The source comment: "This classic algorithm due to Floyd (1964) is known to be O(size)". - **`addAll` does not heapify.** `AbstractQueue`, which provides it, adds each element in turn, so every element sifts up. On 100,000 descending `Comparable` keys at JDK 27, the constructor made 199,978 comparisons and `addAll` on a presized queue made 1,468,946. - **No constructor takes both a collection and a comparator**, so the plain route for a comparator-ordered load from a list is `addAll` or an `offer` loop. - **Heapify runs elsewhere too:** after `removeIf`, `removeAll` or `retainAll` have removed something, and on deserialization.
- Why does PriorityQueue.poll sift the last array element down rather than just promoting the smaller child until the hole reaches a leaf?Promotion alone would leave the hole at an arbitrary leaf, and a gap in the array breaks the index arithmetic that assumes a complete tree. The last used slot is the one that can be vacated with no gap, so its element fills the root and finds its level, and the loop stops early as soon as it is no larger than the smaller child.
- How do you load a list into a comparator-ordered PriorityQueue, given that no constructor takes both a collection and a comparator?The plain route is `new PriorityQueue<>(Math.max(1, n), cmp)` and then `addAll` or an `offer` loop; a capacity below 1 throws, so an empty list needs the guard. Presizing avoids array copies, but each element still sifts up, so the worst case is O(n log n). To get `heapify`, use natural ordering, for instance a wrapper type whose `compareTo` applies the comparator, or a `PriorityQueue` subclass that carries the comparator and returns the list's elements from `toArray`.
- Why can PriorityQueue.remove(Object) need to sift up as well as down, when poll only ever sifts down?Package-private `removeAt` fills the hole with the last element, which may come from another branch of the tree. If it sifts down and stays put, it can still be smaller than the hole's parent, so it then sifts up. `poll` never faces this because its hole is the root, which has no parent. At JDK 27, removing 11 from `[1, 10, 2, 11, 12, 3, 4]` leaves `[1, 4, 2, 10, 12, 3]`.
- PriorityQueue keeps its backing array fully sorted, re-sorting it on every offer.
- The heap is a linked structure of node objects with left and right child pointers.
- poll only promotes the smaller child at each level and never touches the last array element.
- addAll on an existing PriorityQueue runs heapify, so it costs O(n) like the constructor.
- Every PriorityQueue bulk constructor runs heapify, including the SortedSet one.
- PriorityQueue's array always exactly doubles when full and shrinks again as elements are polled.
- java.util.PriorityQueue
- Java 1.5
Assumes JDK 27; the growth numbers describe the implementation, which the Javadoc leaves unspecified, and PriorityQueue.java is identical at JDK 25.
context
- PriorityQueue (Java SE 27 & JDK 27)docs.oracle.com
- AbstractQueue (Java SE 27 & JDK 27)docs.oracle.com
- PriorityQueue.java at jdk-27-gagithub.com