Heaps & Priority Queues

The heap property

A binary heap is a binary tree with two rules. First, the shape rule: the tree is complete, meaning every level is full except possibly the last, which fills left to right, no gaps. Second, the ordering rule, called the heap property: in a min-heap, every parent is less than or equal to its children. A max-heap flips it, with every parent greater than or equal to its children.

Notice how much weaker this is than the BST rule. A BST orders left against right; a heap only orders parent against child. Siblings can be in any order, and you cannot search a heap efficiently. That weakness is the point: the heap gives up ordering it does not need in exchange for speed and simplicity on the one thing it does. The minimum of a min-heap is always sitting at the root, readable in O(1).

When you insert, the new value goes in the next open slot on the bottom level, then bubbles up: swap with the parent while it is smaller. When you remove the minimum, the last element moves to the root, then sinks down: swap with the smaller child while a child beats it. Both walks travel at most the height of the tree, and a complete tree with n nodes has height around log n, hence O(log n) per update.

A tree that lives inside an array

Here is the elegant implementation trick: because the tree is complete, it can live in a plain array with no left or right references at all. Number the nodes top to bottom, left to right, and store them at those array indices. For a node at index i, its left child is at index 2 * i + 1, its right child at 2 * i + 2, and its parent at (i - 1) / 2 using integer division.

The completeness rule is what makes this work, since there are no gaps in the tree, there are no wasted slots in the array. Bubbling up and sinking down become pure index arithmetic: compare, swap array elements, recompute an index. No node objects, no null checks, great memory locality.

You will rarely hand-roll a heap in an interview, but the index formulas do get asked, and they explain what the library is doing under the hood.

int parent(int i) {
    return (i - 1) / 2;
}

int leftChild(int i) {
    return 2 * i + 1;
}

int rightChild(int i) {
    return 2 * i + 2;
}

PriorityQueue: Java's built-in heap

In Java the heap comes ready-made as java.util.PriorityQueue, which is a min-heap by default: peek and poll always deal with the smallest element. The three methods to know are offer (insert, O(log n)), peek (look at the minimum without removing it, O(1)), and poll (remove and return the minimum, O(log n)).

Need a max-heap? Pass a comparator that reverses the order, most simply Collections.reverseOrder(). For objects, supply a comparator describing the priority, for example, ordering int arrays by their first element. One warning: iterating a PriorityQueue with a for-each loop does not produce sorted order, because the heap only guarantees where the root is. To consume elements in priority order, poll repeatedly.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.peek());
System.out.println(minHeap.poll());

PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(9);
System.out.println(maxHeap.peek());

The classic use case: top K

The heap's signature interview pattern is the top-K problem: from a huge stream of values, keep the K largest. Sorting everything costs O(n log n) and needs all the data at once. A heap does better with a counterintuitive twist: to track the K largest elements, use a min-heap of size K.

Why a min-heap? Because its root is the smallest of your current top K. The weakest member of the club, and the only one a newcomer needs to beat. For each incoming value, offer it, and if the heap's size exceeds K, poll once to evict that weakest member. After the whole stream, the heap holds exactly the K largest values, at a cost of O(n log k) time and only O(k) memory.

Heaps assume you only care about one extreme at a time. The next structure, the trie, has a completely different specialty. It organizes strings character by character so that prefix lookups become nearly free.

int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) heap.poll();
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) result[i] = heap.poll();
    return result;
}

Frequently asked