PriorityQueue

the picture

you know how a hospital emergency room doesn't serve patients in arrival order? whoever's worst goes next. but nobody keeps the whole waiting room in perfect order either: they just make sure they always know who's worst right now. that's a priority queue, and the trick that makes it cheap is the heap.

a heap is a tree with one rule: every parent beats its children (for a min-heap: is smaller or equal). nothing is promised between siblings or cousins. so the root is always the overall winner, and fixing the tree after a change only takes one path from top to bottom.

and the tree doesn't need any pointers. store it level by level in an array and the arithmetic does the linking:

• the children of index i are at 2i + 1 and 2i + 2
• the parent of i is at (i - 1) >>> 1

sift up, sift down

offer(x): put x in the first free slot (the end of the array, the bottom-left-most free spot of the tree). while it beats its parent, swap them. at most one swap per level, so O(log n).

poll(): the answer is queue[0]. to fill the hole, take the last element (removing it is free), put it at the root, and while it loses to its better child, swap them. again one path, O(log n).

peek(): queue[0]. O(1).

the real code in jdk 25 (siftUpComparable, siftDownComparable) doesn't actually swap. it carries the moving element in a local variable, slides parents (or children) into the hole, and writes the element once at the end. same comparisons, fewer writes.

void main() {
    var pq = new PriorityQueue<Integer>();
    for (int x : new int[] {5, 1, 4, 2, 3}) pq.offer(x);
    IO.println(pq + " peek=" + pq.peek());
    var out = new StringBuilder();
    while (!pq.isEmpty()) out.append(pq.poll()).append(' ');
    IO.println(out.toString().trim());
}

[1, 2, 4, 5, 3] peek=1
1 2 3 4 5

comparators: max-heaps and real objects

a PriorityQueue is a min-heap by natural order. anything else is a Comparator:

void main() {
    int k = 3;
    var top = new PriorityQueue<Integer>();
    for (int x : new int[] {5, 1, 9, 3, 7, 2, 8}) {
        top.offer(x);
        if (top.size() > k) top.poll();
    }
    var max = new PriorityQueue<Integer>(Comparator.reverseOrder());
    max.addAll(List.of(5, 1, 9, 3));
    IO.println(top.peek() + " " + new TreeSet<>(top) + " " + max.poll());
}

7 [7, 8, 9] 9

the first half is the classic top-k trick: to keep the k largest, use a min-heap of size k and evict its smallest whenever it grows past k. what's left is the k largest, and peek() is the k-th largest. O(n log k) time, O(k) memory, works on a stream you can't hold in memory.

record Task(String name, int priority) {}
 
void main() {
    var pq = new PriorityQueue<Task>(Comparator.comparingInt(Task::priority));
    for (String n : List.of("a", "b", "c", "d", "e", "f")) pq.offer(new Task(n, 1));
    var out = new StringBuilder();
    while (!pq.isEmpty()) out.append(pq.poll().name());
    IO.println(out);
}

what it costs

the array starts at 11 slots and grows like ArrayDeque's: roughly doubling while small (under 64), then by 50%. null elements are rejected (poll uses null to mean empty). it isn't thread-safe; for producer/consumer work there's PriorityBlockingQueue (see concurrent collections).