Heaps and Priority Queues

1Binary heap: complete tree + order property

A binary heap is a complete binary tree — every level filled left to right — stored so the extreme element sits at the root. In a min-heap every parent is \leq its children; in a max-heap every parent is \geq its children. Completeness keeps the tree height \lfloor \log_2 n \rfloor; the order property makes peek-min or peek-max O(1).

The heap is not a BST: in-order traversal is not sorted. Only the root is guaranteed extreme; the second-smallest (in a min-heap) may sit in either subtree.

Figure. Root 1 is the minimum. Every parent is ≤ its children; the tree is complete. In-order is 7, 3, 4, 1, 5, 2 — not sorted.

What the shape guarantees

1. Complete treeNodes pack left to right; height is \Theta(\log n).
2. Heap orderMin-heap: parent ≤ children. Max-heap: parent ≥ children.
3. PeekRead index 0 (the root) in O(1) — no walk.

2Array layout: children at 2i+1 and 2i+2

Because the tree is complete, a heap stores nodes in an array in level order with no gaps. For the node at index i (0-based), the left child is at 2i+1, the right child at 2i+2, and the parent at \lfloor (i-1)/2 \rfloor. No explicit child pointers are required.

Navigating by index arithmetic is O(1) per hop; a sift walks O(\log n) hops along a root-to-leaf path.

Figure. Cells store value after index. Parent of index 5 is 2; children of 1 are 3 and 4 — matching the tree.

From index to family

1. Childrenleft = 2i+1, right = 2i+2 (if those indices are < n).
2. Parentparent = \lfloor (i-1)/2 \rfloor for i > 0.
3. RootIndex 0 has no parent; it is the extreme element.

3Insert and sift-up

Insert writes the new value at the next free leaf position (the end of the array) to preserve completeness, then sifts up: while the node is smaller than its parent in a min-heap (or larger in a max-heap), swap with the parent. At most one swap per level, so insert is O(\log n).

Peek stays O(1) — you do not rebuild the tree; you only repair the single path from the new leaf toward the root.

Insert into a min-heap

1. AppendPlace the value at index n, then n++.
2. Compare upwardWhile i > 0 and a[i] < a[parent(i)], swap them and set i = parent(i).
3. StopHeap order restored on that path; height bounds the swaps by O(\log n).

4Extract-min/max and sift-down

Extract-min on a min-heap returns the root, moves the last leaf into the root hole (to keep the tree complete), then sifts down: repeatedly swap the node with its smaller child while heap order is violated. Extract-max on a max-heap is symmetric. Cost O(\log n); peek without removal stays O(1).

Deleting an arbitrary interior node is not the common API — priority queues expose extract of the extreme element. Arbitrary delete needs an index handle and the same sift repair.

On the Binary heap: complete tree + order property tree, pull the root, move the last leaf into its place, then sift that value down by swapping with the smaller (min-heap) child until order returns.

Extract-min

1. Read rootAnswer = a[0].
2. Fill the holeMove a[n−1] to a[0], then n−−.
3. Sift downWhile a child is smaller than the node, swap with the smaller child; stop at a leaf or when order holds.

5Build-heap is O(n), not O(n log n)

Heapifying an existing array bottom-up calls sift-down from the last internal node up to the root. Naively, n inserts would be O(n \log n), but most nodes sit near the leaves and sift only a short distance. The tight bound sums to O(n).

Interview takeaway: converting an unordered array into a heap is linear. Heap sort still pays O(n \log n) overall because it extracts n times after the build.

Figure. Floyd build-heap siftdown from the first non-leaf is linear; n separate inserts pay an extra \log n factor.

Bottom-up heapify

1. Start at last parenti = \lfloor n/2 \rfloor - 1 down to 0.
2. Sift eachsift-down(i) repairs the subtree rooted at i.
3. BoundAggregate sift cost across heights is O(n), not O(n \log n).

6K-th largest with a size-k min-heap

To find the k-th largest element, maintain a min-heap of size at most k. Push each array value; whenever the heap exceeds size k, pop the smallest. After one pass, the heap holds the k largest values seen, and its root — the smallest among them — is the k-th largest overall.

Time O(n \log k) and space O(k). When k \ll n this beats sorting the whole array in O(n \log n).

Figure. Track the k largest seen so far in a size-k min-heap: the root is the current k-th largest gate.

Size-k filter

1. PushInsert the next element into the min-heap.
2. TrimIf size > k, extract-min (drop a value that cannot be among the k largest).
3. FinishRoot of the size-k heap is the k-th largest.

K-th largest via min-heap

import heapq
def kth_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]

Coding lab. Find the 2nd largest in six numbers runs in the app, with checks on your output.

7Merge k sorted lists with a heap

To merge k sorted linked lists, push each list's head into a min-heap keyed by node value (at most k entries). Repeatedly pop the smallest node, append it to the result, and push that node's successor if it exists. Every node is pushed and popped once.

Total time O(N \log k) for N nodes overall — each heap operation is O(\log k), not O(\log N), because the heap never holds more than one candidate per list.

Figure. One heap entry per list head; each pop emits the next global min and pushes that list's successor — O(n\log k).

k-way merge

1. SeedPush the head of each non-empty list into a min-heap.
2. Pop / appendExtract-min; write that value next in the merged output.
3. RefillIf that node has a next, push next; repeat until the heap is empty.

Merge k lists (heap of heads)

import heapq
def merge_k_lists(lists):
    h = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(h, (node.val, i, node))
    dummy = cur = Node(0)
    while h:
        val, i, node = heapq.heappop(h)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(h, (node.next.val, i, node.next))
    return dummy.next

8Where priority queues show up

Heaps power Dijkstra's algorithm (extract nearest unsettled vertex), heap sort, k-largest/k-smallest filters, and the two-heap streaming median (max-heap for the lower half, min-heap for the upper). Anytime you need repeated "give me the current extreme" under inserts, reach for a priority queue.

If you only need a one-shot minimum of a static array, a linear scan is O(n) and simpler. The heap pays off when extremes are requested many times as the set changes.

Figure. Priority queues show up wherever you repeatedly need the current best edge, task, or candidate — not as a sorted array substitute.