Heaps and PriorityQueue in Java

A heap is a complete binary tree with one ordering rule:

In a max-heap, every parent is greater than or equal to its children, so the largest value is at the root.
In a min-heap, every parent is less than or equal to its children, so the smallest value is at the root.

"Complete" means every level is full except possibly the last, which fills from left to right. That's what lets a heap live in a plain array with no pointers.

graph TB
    a["9 (index 0)"] --> b["7 (index 1)"]
    a --> c["8 (index 2)"]
    b --> d["3 (index 3)"]
    b --> e["5 (index 4)"]
    c --> f["6 (index 5)"]

Text

array:  [9, 7, 8, 3, 5, 6]

for the node at index i:
  parent       = (i - 1) / 2
  left child   = 2i + 1
  right child  = 2i + 2

The heap rule only relates parents and children. Siblings can be in any order (7 and 8 above), so a heap isn't sorted. It only guarantees where the maximum is.

How push and pop work

push (sift up): add the new value at the end of the array, then swap it with its parent while it's larger than the parent.

Text

push 10 into [9, 7, 8, 3, 5, 6]:
[9, 7, 8, 3, 5, 6, 10]   10 is at index 6, parent index 2 holds 8: swap
[9, 7, 10, 3, 5, 6, 8]   10 is at index 2, parent index 0 holds 9: swap
[10, 7, 9, 3, 5, 6, 8]   10 is at the root: done

pop (sift down, in a max-heap): take the root, move the last element to the root, then swap it with its larger child while it's smaller than that child.

Text

pop from [10, 7, 9, 3, 5, 6, 8] returns 10:
[8, 7, 9, 3, 5, 6]       last element 8 moved to the root; children 7 and 9: swap with 9
[9, 7, 8, 3, 5, 6]       8 is at index 2, child index 5 holds 6: done

Both walk one path between the root and a leaf, which is O(log n) long.

`PriorityQueue` is a min-heap

java.util.PriorityQueue stores a binary heap in an array. With no comparator, it orders elements by their natural order, so the smallest element is at the head. Collections.reverseOrder() returns a comparator with the opposite order, which makes a max-heap.

Java

import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        heap.addAll(List.of(3, 9, 5, 7));
        heap.add(8);
        System.out.println("peek = " + heap.peek() + ", size = " + heap.size());
        StringBuilder sb = new StringBuilder();
        while (!heap.isEmpty()) {
            sb.append(heap.poll()).append(' ');
        }
        System.out.println(sb.toString().trim());
    }
}

Output

peek = 9, size = 5
9 8 7 5 3

Operation	Method	Time
add	`add(x)` or `offer(x)`	`O(log n)`
remove the head	`poll()` returns `null` when empty; `remove()` throws `NoSuchElementException`	`O(log n)`
read the head	`peek()` returns `null` when empty	`O(1)`
build from a collection	`new PriorityQueue<>(collection)`	`O(n)`
remove or find an arbitrary value	`remove(x)`, `contains(x)`	`O(n)`
all elements in order	call `poll()` until empty	`O(n log n)`

PriorityQueue rejects null elements. Iterating it with a for-each loop or printing it with toString walks the underlying array, so the order is not sorted:

Java

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int x : new int[]{3, 9, 5, 7}) {
            heap.add(x);
        }
        System.out.println(heap);        // array order
        System.out.println(heap.peek()); // the smallest
    }
}

Output

[3, 7, 5, 9]
3

A min-heap and a max-heap with comparators

A min-heap needs no comparator. A max-heap needs a reversed one. Build comparators with Comparator.comparingInt, Comparator.reverseOrder(), or Integer.compare. Do not write (a, b) -> a - b: the subtraction overflows for values far apart, such as Integer.MAX_VALUE and a negative number, and the heap then misorders them.

Java

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int x : new int[]{3, 9, 5, 7}) {
            minHeap.add(x);
            maxHeap.add(x);
        }
        System.out.println("smallest = " + minHeap.peek() + ", largest = " + maxHeap.peek());

        // Overflow with subtraction: MAX_VALUE - (-1) wraps to a negative number.
        Comparator<Integer> broken = (a, b) -> a - b;
        System.out.println(broken.compare(Integer.MAX_VALUE, -1) < 0);               // wrong: reports MAX_VALUE as smaller
        System.out.println(Integer.compare(Integer.MAX_VALUE, -1) < 0);              // correct
    }
}

Output

smallest = 3, largest = 9
true
false

Priorities with a comparator

A PriorityQueue of objects needs a comparator or Comparable elements. Comparator.comparingInt(Task::priority) orders by one field, and thenComparing breaks ties with a second field. record is a short class declaration whose fields are fixed at construction.

Java

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    record Task(int priority, String name) {}

    public static void main(String[] args) {
        // Lowest priority number first.
        PriorityQueue<Task> tasks = new PriorityQueue<>(
                Comparator.comparingInt(Task::priority).thenComparing(Task::name));
        tasks.add(new Task(3, "write tests"));
        tasks.add(new Task(1, "fix outage"));
        tasks.add(new Task(2, "review PR"));
        while (!tasks.isEmpty()) {
            Task t = tasks.poll();
            System.out.println(t.priority() + ": " + t.name());
        }
    }
}

Output

1: fix outage
2: review PR
3: write tests

A PriorityQueue<Double> works, because Double.compareTo gives a total order that places NaN above every other value. The order of equal-priority elements that the comparator does not separate is unspecified, so add a tie-breaker field when the output must be the same every time.

Replacing the top

PriorityQueue has no method that modifies the head in place. Replacing the largest element means poll() followed by add(), two O(log n) operations. Changing the fields of an element that is already inside the queue does not move it, so the heap order can become wrong. Remove the element (O(n)), change it, and add it again.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        heap.addAll(List.of(5, 8, 2));
        heap.poll(); // remove the max (8)
        heap.add(1); // replace it with 1
        List<Integer> sorted = new ArrayList<>(heap);
        Collections.sort(sorted);
        System.out.println(sorted);
    }
}

Output

[1, 2, 5]

Heap patterns

Problem	Heap to use	Why
`k` smallest elements	max-heap of size `k` (`Comparator.reverseOrder()`)	the head is the largest of the `k` kept, so it's the one to evict
`k` largest elements	min-heap of size `k` (default order)	the head is the smallest of the `k` kept
merge `k` sorted lists	min-heap of `(value, list index)`	always take the smallest front element
process the cheapest item next (Dijkstra)	min-heap of `(cost, node)`	the next item is always the cheapest
running median	a max-heap for the lower half and a min-heap for the upper half	both middle values are at the heads

The lessons in this section cover the first two patterns and the array representation.

How push and pop work

PriorityQueue is a min-heap

A min-heap and a max-heap with comparators

Priorities with a comparator

Replacing the top

Heap patterns

`PriorityQueue` is a min-heap