Heaps and Priority Queues

Why a heap?

A priority queue is a collection where you can always get at (and remove) the element with the highest priority — the smallest number, the most urgent task, the earliest event. You met java.util.PriorityQueue in the Collections chapter; this chapter opens it up.

The obvious implementations are all lopsided:

Implementation	insert	peek at best	remove best
Unsorted array/list	O(1)	O(n)	O(n)
Sorted array/list	O(n)	O(1)	O(1) (from the end)
Binary heap	O(log n)	O(1)	O(log n)

A heap gives up full sorting — it only guarantees that the best element is at the top — and in exchange every operation is logarithmic. For n = 1 000 000, log₂ n is only about 20: an insert moves an element at most about 20 levels.

Complete binary trees stored in an array

A complete binary tree is filled level by level, left to right, with no gaps; only the last level may be partly full, and its nodes are packed to the left. Because there are no gaps, you can number the nodes in level order and store them in an array — no Node objects, no left/right references.

level order:  index 0 1 2 3 4 5 6 7 8
                    90 70 80 30 60 50 40 10 20

                 90            <- index 0
              /      \
            70        80       <- 1, 2
           /  \      /  \
         30    60   50   40    <- 3, 4, 5, 6
        /  \
      10    20                 <- 7, 8

With 0-based indices:

From index i	Formula
parent	(i − 1) / 2 (integer division)
left child	2i + 1
right child	2i + 2
i is a leaf	2i + 1 ≥ n, i.e. i ≥ n / 2

Check the formulas on the tree above (n = 9):

i	value	parent index → value	children indices → values
0	90	none (root)	1, 2 → 70, 80
1	70	(1−1)/2 = 0 → 90	3, 4 → 30, 60
3	30	(3−1)/2 = 1 → 70	7, 8 → 10, 20
4	60	(4−1)/2 = 1 → 70	9, 10 → none: 9 ≥ n, so 60 is a leaf
8	20	(8−1)/2 = 3 → 30	none (leaf, 8 ≥ 9/2)

A complete tree with n nodes has height ⌊log₂ n⌋ (counting edges), so any walk from the root to a leaf or back touches at most about log₂ n + 1 nodes. That is where all the O(log n) costs come from.

The heap property

• Max-heap: every node is ≥ each of its children. The maximum is at index 0.
• Min-heap: every node is ≤ each of its children. The minimum is at index 0.

The property is only between parent and child. Siblings are unordered, and a heap is not a sorted array: [90, 70, 80, 30, 60, 50, 40, 10, 20] is a max-heap even though 80 comes after 70. (The reverse is true, though: an array sorted ascending is always a valid min-heap.)

In a max-heap the minimum can only be at a leaf — a node with a child cannot be the smallest — so finding it means scanning the last ⌈n/2⌉ positions: O(n).

To check an array quickly, compare every non-root position with its parent:

static boolean isMaxHeap(int[] a, int n) {
    for (int i = 1; i < n; i++) {
        if (a[(i - 1) / 2] < a[i]) return false;   // child bigger than parent
    }
    return true;
}

Example: is [50, 30, 40, 35, 10] a max-heap? Index 3 (35) has parent (3−1)/2 = 1, which holds 30. 30 < 35, so no. Drawing it makes the problem obvious:

        50
       /  \
     30    40
    /  \
  35    10        <- 35 is bigger than its parent 30

Insert: add at the end, then sift up

1. Append the new element at index n (the next free slot keeps the tree complete).
2. Sift up (also called percolate up or bubble up): while the element is better than its parent, swap them.

Inserting 75 into the max-heap above: 75 lands at index 9, whose parent is index 4 (60). 75 > 60, swap. Now at index 4, parent index 1 (70): swap. Now at index 1, parent index 0 (90): 75 < 90, stop. Two swaps; result [90, 75, 80, 30, 70, 50, 40, 10, 20, 60].

Step by step, with the tree:

1. append at index 9               2. 75 > 60: swap (index 9 <-> 4)
            90                                 90
         /      \                           /      \
       70        80                       70        80
      /  \      /  \                     /  \      /  \
    30    60   50   40                 30    75   50   40
   / \   /                            / \   /
  10 20 75                           10 20 60
[90,70,80,30,60,50,40,10,20,75]     [90,70,80,30,75,50,40,10,20,60]

3. 75 > 70: swap (index 4 <-> 1)   4. 75 < 90: stop
            90
         /      \
       75        80
      /  \      /  \
    30    70   50   40
   / \   /
  10 20 60
[90,75,80,30,70,50,40,10,20,60]

Sift-up climbs at most the height of the tree: O(log n).

Remove the root: move the last element up, then sift down

1. Save the root (the answer).
2. Move the last element into index 0 and shrink the size by one (the tree stays complete).
3. Sift down: while the element has a child that is better than it, swap it with the better of its two children (the larger in a max-heap, the smaller in a min-heap).

private void siftDown(int i) {               // max-heap version
    while (2 * i + 1 < size) {
        int child = 2 * i + 1;               // left child
        if (child + 1 < size && a[child + 1] > a[child]) child++;   // right is larger
        if (a[i] >= a[child]) break;         // heap property restored
        swap(i, child);
        i = child;
    }
}

Removing the root of [90, 70, 80, 30, 60, 50, 40, 10, 20]: 20 moves to the top; its children are 70 and 80, so it swaps with 80; its new children are 50 and 40, so it swaps with 50; it is now a leaf. Result [80, 70, 50, 30, 60, 20, 40, 10].

Step by step:

1. save 90; move last (20) to the top    2. children 70, 80: bigger is 80, swap
            20                                   80
         /      \                             /      \
       70        80                         70        20
      /  \      /  \                       /  \      /  \
    30    60   50   40                   30    60   50   40
   /                                    /
  10                                   10
[20,70,80,30,60,50,40,10]              [80,70,20,30,60,50,40,10]

3. children 50, 40: bigger is 50, swap   4. index 5 has no children: stop
            80
         /      \
       70        50
      /  \      /  \
    30    60   20   40
   /
  10
[80,70,50,30,60,20,40,10]

Remove the root once more (answer 80): the last element 10 goes to the top, swaps with 70 (bigger of 70 and 50), then with 60 (bigger of 30 and 60). Result [70, 60, 50, 30, 10, 20, 40]. Each removal returns the next-largest value: 90, 80, 70, …

Building a heap bottom-up in O(n)

Given n elements already in an array, you could insert them one by one: n × O(log n) = O(n log n). Floyd's bottom-up build is faster: every leaf is already a one-element heap, so sift down each internal node, from the last one (index n/2 − 1) back to the root.

for (int i = n / 2 - 1; i >= 0; i--) {
    siftDown(a, i, n);
}

Building a max-heap from [3, 9, 2, 1, 4, 5, 8]: index 2 (2) swaps with 8; index 1 (9) is already larger than 1 and 4; index 0 (3) swaps with 9 and then with 4. Result [9, 4, 8, 1, 3, 5, 2]. (Inserting the same values one at a time gives a different — equally valid — heap, [9, 4, 8, 1, 3, 2, 5].)

Step by step (n = 7, so the internal nodes are indices 2, 1, 0):

start                        sift down index 2 (value 2): children 5, 8 -> swap with 8
        3                            3
      /   \                        /   \
     9     2                      9     8
    / \   / \                    / \   / \
   1   4 5   8                  1   4 5   2
[3, 9, 2, 1, 4, 5, 8]          [3, 9, 8, 1, 4, 5, 2]

sift down index 1 (value 9):   sift down index 0 (value 3):
children 1, 4 -> 9 is bigger,  children 9, 8 -> swap with 9; then children 1, 4 -> swap with 4
nothing to do
        3                            9
      /   \                        /   \
     9     8                      4     8
    / \   / \                    / \   / \
   1   4 5   2                  1   3 5   2
[3, 9, 8, 1, 4, 5, 2]          [9, 4, 8, 1, 3, 5, 2]

For comparison, inserting 3, 9, 2, 1, 4, 5, 8 one at a time (append + sift-up each time):

insert	heap afterwards
3	[3]
9	[9, 3]
2	[9, 3, 2]
1	[9, 3, 2, 1]
4	[9, 4, 2, 1, 3]
5	[9, 4, 5, 1, 3, 2]
8	[9, 4, 8, 1, 3, 2, 5]

Why O(n)? The cost of sifting down a node is its height, not the height of the tree. Half of the nodes are leaves and cost nothing; a quarter sit one level up and move at most 1 step; an eighth move at most 2 steps, and so on:

n/4 · 1 + n/8 · 2 + n/16 · 3 + … = n · Σ h/2^(h+1) ≤ n

The many cheap nodes are at the bottom; only a handful of nodes near the root are expensive. Insert-one-at-a-time is the opposite: most elements arrive at the bottom and may have to climb the whole height.

Heap sort

Heap sort (outlined in the sorting chapter) is now easy to state in full:

1. Build a max-heap in the array, bottom-up: O(n).
2. Repeat for end = n − 1 down to 1: swap a[0] (the current maximum) with a[end], then sift down index 0 within the first end elements.

The sorted part grows from the right; the heap shrinks from the left. Ascending order needs a max-heap because the largest element must go to the end.

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;   // max goes to its final place
        siftDown(a, 0, end);                        // heap is now a[0..end-1]
    }
}

Trace on [4, 10, 3, 5, 1]:

Step	Array (heap part │ sorted part)
after build	10 5 3 4 1 │
pass 1	5 4 3 1 │ 10
pass 2	4 1 3 │ 5 10
pass 3	3 1 │ 4 5 10
pass 4	1 │ 3 4 5 10

The same trace with every swap shown:

step	what happens	array afterwards
build: i = 1	10 ≥ its child 5 (index 3) and 1 (index 4): nothing	[4, 10, 3, 5, 1]
build: i = 0	4 swaps with bigger child 10, then with bigger child 5	[10, 5, 3, 4, 1]
pass 1, swap	a[0] ↔ a[4]: 10 goes to its final place	[1, 5, 3, 4 │ 10]
pass 1, sift	1 swaps with 5, then with 4	[5, 4, 3, 1 │ 10]
pass 2, swap	a[0] ↔ a[3]	[1, 4, 3 │ 5, 10]
pass 2, sift	1 swaps with 4 (bigger of 4 and 3)	[4, 1, 3 │ 5, 10]
pass 3, swap	a[0] ↔ a[2]	[3, 1 │ 4, 5, 10]
pass 3, sift	3 ≥ 1: nothing	[3, 1 │ 4, 5, 10]
pass 4, swap	a[0] ↔ a[1]	[1 │ 3, 4, 5, 10]

Property	Heap sort
Time (best, average, worst)	O(n log n)
Extra space	O(1) — in place
Stable?	No — the long-distance swap with a[end] can jump an element over its equal twin
Compared with	merge sort (stable, O(n) extra space), quick sort (O(n²) worst case, usually faster in practice)

A generic MyPriorityQueue<E> with a Comparator

A reusable priority queue should not hard-code > on int. Store the elements in an ArrayList<E> and let a Comparator<? super E> decide who is "better". Following Java's convention, the queue is a min-heap with respect to the comparator: the element that compares smallest comes out first; pass a reversed comparator to get a max-heap.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.NoSuchElementException;

public class MyPriorityQueue<E> {
    private final ArrayList<E> heap = new ArrayList<>();
    private final Comparator<? super E> cmp;

    public MyPriorityQueue(Comparator<? super E> cmp) { this.cmp = cmp; }

    public int size() { return heap.size(); }
    public boolean isEmpty() { return heap.isEmpty(); }

    public E peek() {
        if (heap.isEmpty()) throw new NoSuchElementException();
        return heap.get(0);
    }

    public void offer(E e) {
        heap.add(e);
        int i = heap.size() - 1;
        while (i > 0) {
            int p = (i - 1) / 2;
            if (cmp.compare(heap.get(i), heap.get(p)) >= 0) break;
            swap(i, p);
            i = p;
        }
    }

    public E poll() {
        E top = peek();
        E last = heap.remove(heap.size() - 1);      // O(1): removes the end
        if (!heap.isEmpty()) {
            heap.set(0, last);
            int i = 0, n = heap.size();
            while (2 * i + 1 < n) {
                int c = 2 * i + 1;
                if (c + 1 < n && cmp.compare(heap.get(c + 1), heap.get(c)) < 0) c++;
                if (cmp.compare(heap.get(i), heap.get(c)) <= 0) break;
                swap(i, c);
                i = c;
            }
        }
        return top;
    }

    private void swap(int i, int j) {
        E t = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, t);
    }
}

Usage with the comparators from the lambdas chapter:

MyPriorityQueue<String> byLength =
        new MyPriorityQueue<>(Comparator.comparing(String::length));
MyPriorityQueue<Integer> maxFirst =
        new MyPriorityQueue<>(Comparator.reverseOrder());

Offering "banana", "fig", "apple", "kiwi" to byLength and polling until empty gives fig kiwi apple banana (lengths 3, 4, 5, 6). Offering 5, 1, 4, 2, 3 to maxFirst and polling gives 5 4 3 2 1.

Notice that poll removes the last element of the ArrayList (O(1)) and puts it at index 0, instead of calling heap.remove(0) (O(n), and it would shift every element and break the tree).

java.util.PriorityQueue — what it really does

• It is a binary min-heap in an array. With no comparator it uses natural ordering (Comparable); new PriorityQueue<>(Comparator.reverseOrder()) gives a max-heap.
• offer/add and poll/remove() are O(log n); peek is O(1); remove(Object) and contains are O(n) because they scan the array.
• Its iterator and toString() follow the internal array, which is heap-ordered, not sorted. Only repeated poll() gives sorted order.
• It is not stable: equal-priority elements do not come out in insertion order. If order of arrival matters, add a sequence number as a tie-breaker.
• Element types must be comparable (or you must pass a comparator). PriorityQueue<int[]> compiles, but adding arrays throws ClassCastException at run time.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[] {5, 1, 4, 2, 3}) pq.add(x);
System.out.println(pq);                 // [1, 2, 4, 5, 3]  -- heap order!
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // 1 2 3 4 5

Where does [1, 2, 4, 5, 3] come from? Follow the min-heap after each add:

add	internal array	what happened
5	[5]	first element
1	[1, 5]	1 < parent 5: swap
4	[1, 5, 4]	4 > parent 1: stays
2	[1, 2, 4, 5]	2 at index 3, parent 5: swap; then parent 1: stop
3	[1, 2, 4, 5, 3]	3 at index 4, parent 2: stays

Applications

Top-k largest / k-th largest. Keep a min-heap of size k holding the k largest values seen so far. For each new value x: if the heap has fewer than k elements, add x; otherwise, if x is larger than the heap's minimum, poll and add x. At the end the heap's peek() is the k-th largest. Cost O(n log k) time and O(k) space — much better than sorting (O(n log n)) when k is small, and it works on a stream you cannot store.

static int kthLargest(int[] a, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap
    for (int x : a) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();   // throw away the smallest
    }
    return heap.peek();
}

The counter-intuitive part: to keep the largest elements you use a min-heap, because the element you need to evict is the smallest of the survivors. Think of a club with only 3 places: when a stronger player arrives, the weakest member has to leave — so you must always know who the weakest member is.

Trace kthLargest([5, 1, 9, 3, 7, 6], 3) (heap contents listed in sorted order for readability):

x	action	heap afterwards	peek
5	offer	{5}	5
1	offer	{1, 5}	1
9	offer	{1, 5, 9}	1
3	offer, size 4 > 3: poll 1	{3, 5, 9}	3
7	offer, poll 3	{5, 7, 9}	5
6	offer, poll 5	{6, 7, 9}	6

The answer is 6: the three largest values are 9, 7, 6, and the smallest of them is the 3rd largest.

Merging k sorted lists. Put the first element of each list into a min-heap together with "which list, which position". Repeatedly poll the smallest, output it, and offer the next element from the same list. The heap never holds more than k entries, so merging n elements in total costs O(n log k).

For example, with the lists [1, 4, 7], [2, 5] and [3, 6]: the heap starts as {1, 2, 3}; poll 1 and offer 4 (from the same list); poll 2 and offer 5; poll 3 and offer 6; then 4, 5, 6, 7 come out in order.

Scheduling by priority. Operating-system schedulers, printer queues, hospital triage, and event-driven simulations (always process the event with the earliest time next) are all priority queues. Dijkstra's shortest-path algorithm, coming later in the course, uses one too.

class Task {
    final String name; final int priority; final long seq;   // seq = arrival number
    Task(String name, int priority, long seq) { this.name = name; this.priority = priority; this.seq = seq; }
}

PriorityQueue<Task> ready = new PriorityQueue<>(
        Comparator.comparingInt((Task t) -> -t.priority)   // higher priority first
                  .thenComparingLong(t -> t.seq));          // then first come, first served

Key takeaways

• A heap is a complete binary tree in an array: parent (i − 1) / 2, children 2i + 1 and 2i + 2. No gaps, so no references are needed.
• Heap property: every parent beats its children (≥ in a max-heap, ≤ in a min-heap). Siblings are not ordered, and a heap is not sorted.
• Insert = append at the end + sift-up. Remove root = move the last element to the top + sift-down, swapping with the better child. Both O(log n); peek is O(1).
• Bottom-up build (sift down indices n/2 − 1 down to 0) costs O(n); inserting one by one costs O(n log n).
• Heap sort = build a max-heap, then repeatedly swap the root to the end and sift down. O(n log n) always, in place, not stable.
• java.util.PriorityQueue is a min-heap; printing or iterating shows heap order, only poll() gives sorted order.
• For the k largest values, keep a min-heap of size k: O(n log k).