Heap & Priority Queue

Phase 1f(x)

The Mathematics

Heap property, array representation, and build-heap analysis

Heap Property

A min-heap is a complete binary tree where every node is smaller than or equal to its children:

\forall\, i: A[i] \leq A[2i+1] \text{ and } A[i] \leq A[2i+2]

This guarantees $A[0] = \min(A)$ — the root is always the minimum.

Array Representation

A complete binary tree maps perfectly to an array using index arithmetic:

$\bullet$ Parent of node $i$ : $\lfloor (i-1)/2 \rfloor$

$\bullet$ Left child: $2i + 1$

$\bullet$ Right child: $2i + 2$

No pointers needed — the tree structure is implicit in the array indices.

Key Operations

Sift Down: If a node violates the heap property, swap it with its smallest child and repeat. Takes $O(\log n)$ .

Build Heap: Call sift-down from the last non-leaf ( $\lfloor n/2 \rfloor - 1$ ) up to the root.

Extract Min: Remove root, replace with last element, sift down. Takes $O(\log n)$ .

Build Heap: O(n), Not O(n log n)

Surprisingly, building a heap takes $O(n)$ , not $O(n \log n)$ . Most nodes are near the leaves and sift down only a few levels:

\sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h) = O(n)

There are $n/2$ leaves (sift 0), $n/4$ nodes at height 1 (sift 1), etc. The sum converges to $O(n)$ .

Phase 2▶

See It Work

Building a min-heap from [4, 10, 3, 5, 1, 8, 2] then extracting min

Array Representation

\text{Build-Heap: sift down from } \lfloor n/2 \rfloor - 1 \text{ to } 0

Building

Step 1 of 10

Start with unordered array. Build a min-heap by sifting down from the last non-leaf node upward.

Phase 3</>

The Code

Mapping heap operations to Python with sift-down

Mathematical Formulation

\text{for } i = \lfloor n/2 \rfloor - 1 \text{ downto } 0

Build heap bottom-up from last non-leaf to root

\text{children}(i) = (2i{+}1,\; 2i{+}2)

In array representation, children are at indices 2i+1 and 2i+2

A[i] > A[\text{child}] \Rightarrow \text{swap}

If parent is larger than smallest child, swap to restore heap

\text{min} = A[0]

Root of min-heap is always the minimum element

\text{extractMin}: O(\log n)

Replace root with last element and sift down — O(log n)

Python Implementation

def build_min_heap(A):
    n = len(A)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(A, i, n)          # Heapify subtree

def sift_down(A, i, n):
    smallest = i
    left, right = 2*i + 1, 2*i + 2
    if left < n and A[left] < A[smallest]:
        smallest = left              # Left is smaller
    if right < n and A[right] < A[smallest]:
        smallest = right             # Right is smaller
    if smallest != i:
        A[i], A[smallest] = A[smallest], A[i]
        sift_down(A, smallest, n)    # Recurse down

def extract_min(A):
    min_val = A[0]                   # Root is min
    A[0] = A[-1]                     # Move last to root
    A.pop()
    sift_down(A, 0, len(A))         # Restore heap
    return min_val