Binary heap / priority queue

How does Binary heap / priority queue work?

A heap is a tree kept inside a flat array. The children of index i sit at 2i plus one and two.

The only rule is that a parent beats its children. Siblings are in no order whatsoever.

A push writes at the end, then bubbles the value up. It swaps with the parent while it wins.

A pop takes the root, moves the last item up there, and sinks it. It swaps with the better child until it fits.

Both moves walk one path of the tree. The height is log n, so both cost log n.

Only the root ever means anything. Every other position is arbitrary.

Sources: Wikipedia: Binary heap, Python docs: heapq

1. [5]Pushing 5, 3 and 8. The first value is the root.
2. [3, 5]3 is pushed and bubbles above the 5.
3. [3, 5, 8]8 stays where it lands. It does not beat its parent.
4. pop returns 3The root is taken away. The last item, 8, moves to the top.
5. [5, 8]8 sinks below the 5. The new root is the smallest left.

function kSmallest(nums, k) {
    const heap = []; // max-heap: keeps the k smallest seen so far
    const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]);
    function push(v) {
        heap.push(v);
        let i = heap.length - 1;
        while (i > 0 && heap[(i - 1) >> 1] < heap[i]) { swap((i - 1) >> 1, i); i = (i - 1) >> 1; }
    }
    function pop() {
        const top = heap[0];
        heap[0] = heap.pop();
        let i = 0;
        while (2 * i + 1 < heap.length) {
            let c = 2 * i + 1;
            if (c + 1 < heap.length && heap[c + 1] > heap[c]) c++;
            if (heap[i] >= heap[c]) break;
            swap(i, c); i = c;
        }
        return top;
    }
    for (const x of nums) {
        push(x);
        if (heap.length > k) pop();
    }
    return heap.slice().sort((a, b) => a - b);
}

function kSmallest(nums: number[], k: number): number[] {
    const heap: number[] = []; // max-heap: keeps the k smallest seen so far
    const swap = (i: number, j: number): void => {
        [heap[i], heap[j]] = [heap[j], heap[i]];
    };
    function push(v: number): void {
        heap.push(v);
        let i = heap.length - 1;
        while (i > 0 && heap[(i - 1) >> 1] < heap[i]) { swap((i - 1) >> 1, i); i = (i - 1) >> 1; }
    }
    function pop(): number {
        const top = heap[0];
        heap[0] = heap.pop()!;
        let i = 0;
        while (2 * i + 1 < heap.length) {
            let c = 2 * i + 1;
            if (c + 1 < heap.length && heap[c + 1] > heap[c]) c++;
            if (heap[i] >= heap[c]) break;
            swap(i, c); i = c;
        }
        return top;
    }
    for (const x of nums) {
        push(x);
        if (heap.length > k) pop();
    }
    return heap.slice().sort((a, b) => a - b);
}

import heapq

def k_smallest(nums, k):
    heap = []  # max-heap via negation: keeps the k smallest seen so far
    for x in nums:
        heapq.heappush(heap, -x)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(-x for x in heap)

function kSmallest(array $nums, int $k): array {
    $heap = new SplMaxHeap(); // keeps the k smallest seen so far
    foreach ($nums as $x) {
        $heap->insert($x);
        if ($heap->count() > $k) {
            $heap->extract();
        }
    }
    $result = [];
    foreach ($heap as $x) {
        $result[] = $x;
    }
    sort($result);
    return $result;
}

    public static List<Integer> kSmallest(int[] nums, int k) {
        // max-heap: keeps the k smallest seen so far
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int x : nums) {
            heap.add(x);
            if (heap.size() > k) heap.poll();
        }
        List<Integer> result = new ArrayList<>(heap);
        Collections.sort(result);
        return result;
    }

    public static List<int> KSmallest(int[] nums, int k) {
        // max-heap via a negated key: keeps the k smallest seen so far
        var heap = new PriorityQueue<int, int>();
        foreach (int x in nums) {
            heap.Enqueue(x, -x);
            if (heap.Count > k) heap.Dequeue();
        }
        var result = new List<int>();
        while (heap.Count > 0) result.Add(heap.Dequeue());
        result.Sort();
        return result;
    }

A worked example of Binary heap / priority queue

The k closest points to the origin

Return the k points that lie closest to the origin.

The list can be far too long to sort, and only k points are wanted.

Keep a heap of size k whose top is the worst point still kept.

Push each point, and pop the top whenever the heap grows past k. What remains is the answer.

function kClosest(points, k) {
    // a max-heap keyed by squared distance: the worst kept point sits on top
    const heap = new MaxHeap((p) => p[0] * p[0] + p[1] * p[1]);

    for (const point of points) {
        heap.push(point);

        if (heap.size() > k) {
            heap.pop(); // drops the farthest, never the closest
        }
    }

    return heap.toArray();
}

When should you use Binary heap / priority queue?

Use Binary heap / priority queue when the problem statement says “always need the current smallest/largest”, “top k elements” or “merge k sorted lists”. A solution built on it usually runs in O(log n) per op.

• •always need the current smallest/largest
• •top k elements
• •merge k sorted lists
• •running median while items keep arriving
• •priority queue / most urgent next

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Binary heap / priority queue confused with?

Binary heap / priority queue is most often confused with Fast sort (merge / quick), Binary search tree, Monotonic deque (sliding window max/min) and Dijkstra's algorithm.

• Fast sort (merge / quick): Sorting gives a full order once. A heap gives the front repeatedly, while data still arrives.
• Binary search tree: A search tree orders every pair of nodes. A heap only promises the root.
• Monotonic deque (sliding window max/min): A deque can drop the element that just expired. A heap has no cheap way to do that.
• Dijkstra's algorithm: Dijkstra is the best-known user of a heap. This page is about the container itself.

Common mistakes with Binary heap / priority queue

• Expecting a sorted array

  Only the root is in any order. Reading the array from front to back gives nonsense.

• Keeping every element for a top-k question

  A heap of size k costs O(n log k). Holding all of them costs more memory for no gain.

• Building the heap the wrong way round

  For the k largest you need a min-heap, so the worst kept sits on top. That is easy to invert.

• Trying to delete an arbitrary element

  A heap has no cheap way to find one. Mark it dead and skip it when it surfaces.

Which interview problems use Binary heap / priority queue?

Interview problems solved with Binary heap / priority queue include Kth largest element in a stream, K closest points to origin, Merge k sorted lists, Top k frequent elements, Task scheduler, Find median from a data stream and Dijkstra's shortest path.

• Kth largest element in a stream: A min-heap of size k, and the root is the answer.
• K closest points to origin: A bounded max-heap over squared distance.
• Merge k sorted lists: The heap holds the front node of every list.
• Top k frequent elements: Counts first, then a heap of size k.
• Task scheduler: The most frequent task goes first each round.
• Find median from a data stream: Two heaps facing each other across the middle.
• Dijkstra's shortest path: The heap decides which node to settle next.

What is the time and space complexity of Binary heap / priority queue?

The target complexity of Binary heap / priority queue is O(log n) per op.

n up to 1e6 gives O(log n) per push or pop. Reading the top alone is O(1).