The Heap

A canteen counter serves people in arrival order. That is the queue from the previous chapter. An emergency room cannot work that way. A patient with a heart attack who arrived five minutes ago goes in before someone who has been waiting an hour with a sprained ankle. The process is called triage: each time a room opens, staff take the most urgent patient. Nobody works out who is second or third most urgent, because the next decision will be made from scratch anyway.

That is the whole job of a heap. In a collection that keeps changing, it reports the minimum (or maximum) in O(1), and it removes that element or inserts a new one in O(log n). The phrase "keeps changing" matters: the data does not arrive all at once, just as patients keep walking in.

Why not simply sort everyone, so the most urgent stands first? You can, but sorting does far more work than the question asks for. Sorting costs O(n log n) and fixes the order of all n elements, while you only need one of them. It also breaks down under updates: inserting a new patient into a sorted array means shifting elements, O(n), which is the cost you met in chapter 1. A heap takes the opposite position. It only maintains which element is the extreme one, and that is why insert and remove are both O(log n).

Two words are often mixed up, so separate them now. A priority queue is an interface: a container you can keep adding to, and from which you can always remove the highest-priority element. A binary heap is the most common implementation of that interface. The relation is the same as between "sorting" and "quicksort". In almost every language, PriorityQueue and heapq are backed by a binary heap, and this chapter builds that engine. They are not synonyms, so this chapter says "heap" for the structure and "priority queue" for the interface.

A heap is a binary tree that follows only two rules. One controls the shape, the other controls the order.

Now the two rules connect. Rule 1 says a complete binary tree has no gap. So you can number the nodes level by level, left to right (the root is 0, the next level is 1 and 2, then 3, 4, 5, 6, and so on) and lay them straight into an array, using the number as the index. Because there is no gap, no array slot is wasted, and no pointer is needed: every parent-child link is computed from the index by three formulas.

You have seen this idea before. In the array chapter, the address of an element is base address + index × element size, also computed rather than stored. A heap applies the same arithmetic one level up, from array elements to tree links. Dropping the pointers buys two concrete things: no extra memory (a linked binary tree stores two pointers per node), and elements laid out contiguously in memory, which is friendlier to the CPU cache (the same benefit as in chapter 1).

A heap has two movements, and they mirror each other. On insert, the new element travels from the bottom upwards, which is called sift up. On removal, an element travels from the top downwards, which is called sift down. Push and pop a few values in the lab below and watch the tree view and the array view change together, since they show the same data. You will see that a heap operation is nothing more than comparing one parent-child pair and swapping when the rule is broken, repeated until no swap is needed.

Now in slow motion. push (insert) takes two steps:

1. 1. Write at the end of the array, which is the next free slot of the complete binary tree. This step keeps the shape rule intact.
2. 2. Sift up: compare the new value with its parent and swap while it is smaller, then compare with the new parent, and so on, until it is not smaller than its parent or it reaches the root. The longest path runs from the bottom level to the root, so the number of swaps is at most the height: O(log n).

pop (remove the extreme) is the mirror image, in three steps:

1. 1. Read the root. That is the answer, the smallest value in a min-heap.
2. 2. Move the last element to the root. Why the last one? Because removing the last slot keeps the tree complete, while removing any other position would leave a gap.
3. 3. Sift down. The value that just arrived at the top is probably too large. Compare it with the smaller of its two children and swap while it is larger, following it down, until it is smaller than both children or it has no child. Again at most the height: O(log n).

Why must sift down pick the smaller child? Suppose you swapped with the larger child instead. That larger child becomes the parent, while its smaller sibling is still below it, so parent ≤ child is broken immediately. Only promoting the smaller child keeps both children below the new parent.

The surprising row is heapify: turning an unordered array into a heap in place costs only O(n). Intuition says "n elements, each may sift down log n levels, so O(n log n)". Press Build from random array in the lab and count the swaps. There are usually far fewer than expected. Here is why:

Here are the movements from §03 as code. There are three real methods: siftUp, siftDown, and the static heapify that builds a heap in O(n). push and pop only combine "change the array" with "repair the heap order". The storage is a plain resizable array, and every parent-child link comes from the three formulas in §02. Cover the code and try to write siftDown from memory. The step that picks the smaller child is the one people get wrong most often.

§04 exists so you understand the mechanism. When you solve problems, use what the language provides. The three differ a lot here. Java has PriorityQueue ready to use. Python has heapq, a set of functions that operate on a plain list. JavaScript has no built-in heap, which is why the previous section asked you to memorise one. Remember two shared traps: Java and Python both default to a min-heap, so a max-heap takes extra work; and iterating a heap does not give you sorted order, so the only way to read the elements in order is to remove them one at a time.

Most heap problems fall into three patterns. 1. Top-K: the k-th largest or smallest value, the k most frequent items, the k nearest points. 2. Repeatedly take the extreme and put something back: each step greedily uses the current extreme value and then inserts an updated value, as in task scheduling, reorganising a string, or smashing stones. 3. Merge k sorted sequences: k linked lists or k rows of a matrix. The three worked examples below take one pattern each. Start with the part of Top-K that surprises everyone.

Task: return the k-th largest element of an array. Duplicates count, so it is not the k-th distinct value. Brute force: sort the whole array in O(n log n) and take the k-th from the end. That passes, but it computes the order of every element to answer a question about one. Standard solution: apply the rule above with a min-heap of size k, where the root is the threshold. Here is the run for k = 2.

Task: return the k most frequent elements of an array. Brute force: count the frequencies, sort by frequency, and take the first k, at O(n log n). Standard solution: this is the first problem where you combine two structures. One structure is not enough, so chain two: a hash map counts each value in O(n) (chapter 6), and then those counts are fed into a min-heap of size k for the Top-K step (this chapter). Note that the heap is ordered by count, so the threshold is the lowest count still in the heap.

Task: merge k sorted linked lists into one sorted list. Brute force: copy every node value into an array, sort it, and rebuild the list, at O(N log N) where N is the total number of nodes. It works, but it throws away the fact that each list is already sorted. Standard solution: when merging sorted sequences, the next value of the answer is always the smallest among the current head nodes. Which structure reports the smallest of a changing set? A min-heap. So the heap holds only the k head nodes: take the smallest, then push the node that follows it.