Heaps & Priority Queues

A priority queue is an abstract data type (ADT) that supports three core operations:

• insert(key, value) — add a new element with a given priority
• find-min() (or find-max) — return the element with the highest priority in O(1)
• extract-min() — remove and return the element with the highest priority

Optionally: decrease-key(handle, new_key) — lower the priority of an existing element (crucial for Dijkstra).

The key insight is that a priority queue does not promise full sorted order. It promises only that the best element is always accessible quickly. This weaker guarantee is exactly what graph algorithms and schedulers need, and it is what allows much faster implementations than a sorted array or balanced BST.

A naive array gives O(1) insert but O(n) extract-min. A sorted array gives O(1) extract-min but O(n) insert. A balanced BST (like a red-black tree) gives O(log n) for both, but with large constant factors and poor cache behavior due to pointer chasing. The binary heap achieves O(log n) insert and extract-min with O(1) find-min, using a plain contiguous array — no pointers, no allocations, cache-friendly.

# Priority queue interface (Python)
from heapq import heappush, heappop

pq = []                        # empty min-heap
heappush(pq, (3, 'task C'))    # insert priority 3
heappush(pq, (1, 'task A'))    # insert priority 1
heappush(pq, (2, 'task B'))    # insert priority 2

print(pq[0])                   # peek min: (1, 'task A'), O(1)
pri, task = heappop(pq)        # extract min: (1, 'task A'), O(log n)

A binary heap is a complete binary tree satisfying the heap property.

Complete binary tree: every level is fully filled except possibly the last, which is filled left-to-right. This shape guarantee is what lets us store the tree in a flat array without any pointers.

Min-heap property: every node's key is ≤ the keys of its children. Equivalently, every node is smaller than its entire subtree. The root is therefore always the minimum.

Max-heap property: every node's key is ≥ its children's keys.

Note carefully what the heap property does not say: there is no ordering between siblings, and no ordering between nodes at the same level that aren't in an ancestor-descendant relationship. This is a partial order, not a total order. A heap is decidedly not a sorted array.

Array representation — The magic trick: for a 1-indexed array, node at index i has:

• Left child at index 2i
• Right child at index 2i + 1
• Parent at index ⌊i/2⌋

For 0-indexed arrays (as in Python and C):

• Left child: 2i + 1
• Right child: 2i + 2
• Parent: ⌊(i − 1)/2⌋

This arithmetic replaces pointers entirely. The complete-tree shape guarantees that these indices are always valid and the array has no gaps. A heap of n elements uses exactly n array slots.

Why does this work? A complete binary tree of n nodes has height ⌊log₂ n⌋. The height bounds the cost of all heap operations: any path from root to leaf has length at most ⌊log₂ n⌋ steps.

# Heap stored as array (0-indexed)
# Tree:        1
#            /   \
#           3     2
#          / \   /
#         7   4 5

heap = [1, 3, 2, 7, 4, 5]

# Index arithmetic (0-based)
def left(i):   return 2*i + 1
def right(i):  return 2*i + 2
def parent(i): return (i - 1) // 2

print(heap[left(0)])    # 3  (left child of root)
print(heap[right(0)])   # 2  (right child of root)
print(heap[parent(3)])  # 3  (parent of index 3 = node 7)

To insert a new key k into a min-heap of size n:

1. Place k at position n (the next available slot at the bottom-right of the tree). The array grows by one.
2. Bubble up: while k is smaller than its parent, swap k with its parent.
3. Repeat until k is at the root, or k ≥ its parent.

Why does this restore the heap property? Before insertion, every node satisfied the property. Placing k at the leaf can only violate the property between k and its parent (k might be smaller). After a swap, k moves up one level; now k's new parent might be too large again, so we check again. Because the original heap was valid, every subtree not on this root-to-leaf path is unaffected. The invariant is restored locally at each step.

Complexity: the bubble-up path has length at most h = ⌊log₂(n+1)⌋, so insert is O(log n).

Analogy: think of inserting a new employee into a corporate hierarchy where everyone must be paid less than their manager. The new employee is placed at the bottom; if they are paid more than their boss, they swap roles. This continues until the pay order is restored.

def heap_insert(heap, key):
    heap.append(key)          # step 1: place at end
    i = len(heap) - 1
    _sift_up(heap, i)

def _sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2          # parent index
        if heap[i] < heap[p]:     # heap property violated
            heap[i], heap[p] = heap[p], heap[i]
            i = p
        else:
            break                  # heap property restored

# Example
h = [1, 3, 2, 7, 4, 5]
heap_insert(h, 0)          # insert 0
print(h)                   # [0, 3, 1, 7, 4, 5, 2]  (0 bubbled to root)

Removing the minimum (the root) is the core extraction operation:

1. Save the root value (the minimum).
2. Move the last element (bottom-right) to the root. Shrink the array by one.
3. Sift-down (heapify-down): while the new root is larger than one of its children, swap it with the smaller child.
4. Repeat until the element is ≤ both children, or is a leaf.

Why the smaller child? Suppose node x has children L and R with L < R, and x > L. If we swap x with R (the larger child), then R becomes the new parent of L — but R > L, violating the heap property at that node. We must always swap with the smaller child to keep the property intact throughout the subtree.

Complexity: the sift-down path has length at most ⌊log₂ n⌋, so extract-min is O(log n).

The combined find-min is O(1) (just read index 0). The elegance is that we never actually delete from the middle of an array — we overwrite the root with the last element and sift, doing at most 2 comparisons per level.

def heap_extract_min(heap):
    if not heap:
        raise IndexError("heap is empty")
    min_val = heap[0]
    last = heap.pop()            # remove last element
    if heap:                     # if heap not now empty
        heap[0] = last           # place it at root
        _sift_down(heap, 0)
    return min_val

def _sift_down(heap, i):
    n = len(heap)
    while True:
        smallest = i
        l, r = 2*i + 1, 2*i + 2
        if l < n and heap[l] < heap[smallest]:
            smallest = l
        if r < n and heap[r] < heap[smallest]:
            smallest = r
        if smallest == i:
            break                # heap property satisfied
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

# Example
h = [1, 3, 2, 7, 4, 5]
print(heap_extract_min(h))   # 1
print(h)                     # [2, 3, 5, 7, 4]

Given n unsorted elements, we want to build a valid heap. The naive approach — inserting each element one by one with heap_insert — takes O(n log n). But there is a beautiful O(n) algorithm.

Floyd's build-heap algorithm:

1. Load all elements into an array (any order).
2. Starting from the last non-leaf (index ⌊n/2⌋ − 1 in 0-based) down to index 0, call sift-down on each node.

Leaves (indices ⌊n/2⌋ through n−1) trivially satisfy the heap property. By calling sift-down bottom-up, when we process node i, both its subtrees are already valid heaps. Sift-down restores the property rooted at i. Working bottom-up ensures correctness.

Why is this O(n) and not O(n log n)? The height of a node at depth d in a complete tree of n nodes is at most h − d, where h = ⌊log₂ n⌋. Sift-down on a node costs O(height of that node). There are at most ⌈n/2^(k+1)⌉ nodes of height k. Summing over all heights:

$$\sum_{k=0}^{h} \frac{n}{2^{k+1}} \cdot k = O(n) \sum_{k=0}^{\infty} \frac{k}{2^k} = O(n) \cdot 2 = O(n)$$

The sum ∑ k/2^k = 2 (a standard geometric series derivative). Most nodes are near the leaves and have small height — the expensive sift-down calls happen at the top, but there are very few such nodes. This is a recurring and important proof technique.

Practical consequence: building a heap from a known array is linear. Python's heapq.heapify uses exactly this algorithm.

def build_heap(arr):
    """Build a min-heap in-place in O(n)."""
    n = len(arr)
    # Start from last non-leaf, go up to root
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i)
    return arr

# Example
data = [9, 4, 7, 1, 8, 3, 6, 2, 5]
build_heap(data)
print(data)   # [1, 2, 3, 4, 8, 7, 6, 9, 5]  — valid min-heap
# Verify: data[0]=1 <= data[1]=2, data[2]=3 ✓

# Python built-in (same algorithm):
import heapq
heapq.heapify(data)  # O(n), in-place

Heapsort is a comparison-based, in-place, O(n log n) worst-case sorting algorithm built directly on heap operations.

Algorithm:

1. Build a max-heap from the input array in O(n).
2. Repeatedly extract the maximum: swap the root (max) with the last element of the heap, shrink the heap by 1, and sift-down the new root.
3. After n−1 extractions, the array is sorted in ascending order.

Why a max-heap for ascending sort? Each extraction places the maximum at the end of the shrinking heap region. After all extractions, the largest elements accumulate at the back of the array — exactly ascending order.

Complexity:

• Build-heap: O(n)
• n extractions, each O(log n): O(n log n)
• Total: O(n log n), in-place, no extra memory beyond O(1)

Heapsort vs. quicksort vs. mergesort:

• Heapsort is the only sort that is simultaneously in-place and O(n log n) worst-case.
• Quicksort is faster in practice (better cache behavior, smaller constants) but O(n²) worst-case without randomization.
• Mergesort is O(n log n) worst-case but requires O(n) extra space.
• Heapsort's weakness is poor cache locality: sift-down accesses elements that are far apart in memory (parent and children differ by a factor of 2), causing many cache misses.

Introspective sort (used in C++ std::sort) combines quicksort, heapsort, and insertion sort: it uses quicksort normally but switches to heapsort if recursion depth exceeds O(log n), guaranteeing O(n log n) worst-case with quicksort's average-case speed.

def heapsort(arr):
    n = len(arr)

    # Step 1: Build max-heap (sift-down with max-heap logic)
    def sift_down_max(arr, i, size):
        while True:
            largest = i
            l, r = 2*i + 1, 2*i + 2
            if l < size and arr[l] > arr[largest]: largest = l
            if r < size and arr[r] > arr[largest]: largest = r
            if largest == i: break
            arr[i], arr[largest] = arr[largest], arr[i]
            i = largest

    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(arr, i, n)

    # Step 2: Extract max repeatedly
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # swap max to back
        sift_down_max(arr, 0, end)            # re-heapify

    return arr

print(heapsort([5, 3, 8, 1, 9, 2, 7]))  # [1, 2, 3, 5, 7, 8, 9]

The priority queue is the algorithmic heart of a wide class of greedy and best-first algorithms.

Dijkstra's Shortest Path Dijkstra's algorithm finds shortest paths from a source vertex s in a weighted graph with non-negative edges. The priority queue holds (distance, vertex) pairs.

• Initialize dist[s] = 0, dist[v] = ∞ for all v ≠ s. Insert all vertices.
• Repeat: extract-min to get the unvisited vertex u with smallest tentative distance. For each neighbor v of u, if dist[u] + w(u,v) < dist[v], update dist[v] and decrease-key (or re-insert) v in the PQ.

With a binary heap: O((V + E) log V). With a Fibonacci heap: O(E + V log V) — faster when E >> V (dense graphs).

OS Process Scheduling Real-time operating systems maintain a priority queue of runnable threads. The scheduler calls extract-min at every context switch (O(log n)). New processes and priority changes call insert and decrease-key. The O(log n) bound ensures scheduling decisions never become the bottleneck.

Event-Driven Simulation A discrete-event simulator maintains a priority queue of events ordered by timestamp. The simulation loop extracts the earliest event, processes it (which may insert future events), and repeats. This is the foundation of network simulators, physics engines, and financial market simulators.

Median Maintenance A classic interview problem: maintain a running median over a stream of numbers. Use two heaps — a max-heap for the lower half and a min-heap for the upper half — keeping them balanced within 1 element. The median is always at the top of one heap. Both insert and find-median are O(log n).

import heapq

def dijkstra(graph, source):
    """graph: dict of {node: [(neighbor, weight), ...]}"""
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    pq = [(0, source)]          # (distance, vertex)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:          # stale entry, skip
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))  # {'A':0,'B':1,'C':3,'D':4}

A d-ary heap generalizes the binary heap: each node has at most d children instead of 2. The array indexing generalizes cleanly:

• Children of node i: di+1, di+2, ..., di+d
• Parent of node i: ⌊(i−1)/d⌋

Trade-offs:

• Sift-up (insert) becomes faster: height is log_d(n) instead of log_2(n). Fewer swaps needed.
• Sift-down (extract-min) becomes slower: at each level, you must compare d children to find the minimum, costing d comparisons per level. Total: O(d · log_d(n)).
• For Dijkstra-like algorithms where decrease-key >> extract-min (e.g., dense graphs), larger d speeds up the algorithm overall.

Cache performance: a 4-ary heap has better cache behavior than a binary heap because more children fit in a cache line. Studies show 4-ary and 8-ary heaps outperform binary heaps in practice on modern hardware.

When to use: choose d ≈ E/V for Dijkstra on a graph with E edges and V vertices — this balances the cost of extract-min and decrease-key to yield the same O(E log_{E/V} V) complexity as a Fibonacci heap for many practical inputs, without the Fibonacci heap's implementation complexity.

# d-ary heap sift-down (extract-min)
def sift_down_d(heap, i, d, n):
    while True:
        smallest = i
        # Check all d children
        for c in range(d*i + 1, min(d*i + d + 1, n)):
            if heap[c] < heap[smallest]:
                smallest = c
        if smallest == i:
            break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

# For a 4-ary heap, d=4
# Height = log_4(n) ≈ 0.5 * log_2(n)
# Each sift-down level costs 4 comparisons vs 2 for binary
# Net: ~2x faster sift-up, ~2x slower sift-down

Many algorithms — Dijkstra, Prim's MST, A* — need to decrease the priority of an existing element already in the heap. This is the decrease-key operation.

In a binary heap, decrease-key requires:

1. Find the element (O(n) naively, or O(1) with a hash map from element to heap index).
2. Lower its key.
3. Sift-up, since the element is now smaller than it should be: O(log n).

Maintaining the index map adds bookkeeping complexity.

Lazy deletion (the pattern used in most practical implementations, including Python's heapq):

• Instead of true decrease-key, insert a new copy of the element with the updated (lower) priority.
• Mark the old copy as stale.
• During extract-min, skip stale entries.

This is why the Dijkstra code shown earlier checks if d > dist[u]: continue. The heap may contain multiple entries for the same vertex; only the one with the current shortest distance is processed.

Cost: the heap may have up to E entries instead of V, so complexity becomes O(E log E) = O(E log V) for Dijkstra. This is acceptable and simpler to implement. In practice, lazy deletion is almost always the right choice over maintaining explicit index maps, unless decrease-key is called far more often than extract-min.

# Lazy deletion pattern in priority queue
from heapq import heappush, heappop

def dijkstra_lazy(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heappop(pq)
        # Key lazy check: skip if we have a better dist already
        if d > dist[u]:
            continue              # stale entry, discard
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heappush(pq, (nd, v))   # new entry, old one is now stale
    return dist

The Fibonacci heap is an advanced priority queue that achieves better amortized bounds than any binary or d-ary heap:

The O(1) amortized decrease-key is what makes Dijkstra run in O(E + V log V) instead of O((E + V) log V) — a difference that matters for dense graphs.

Core idea: Fibonacci heaps use a forest of heap-ordered trees (not just one tree). Insert and decrease-key are lazy — they just add a new tree or cut a node, deferring cleanup. Consolidation (merging trees of equal degree) is deferred until extract-min. The name comes from the fact that a Fibonacci heap tree of degree k has at least F(k+2) nodes (a Fibonacci number), which gives the O(log n) bound on the maximum degree.

Amortized analysis: the potential function Φ = (number of trees) + 2×(number of marked nodes). Insert costs O(1) actual + increases Φ by 1. Extract-min is expensive (consolidates the forest) but reduces Φ significantly, amortizing the cost.

Practical note: Fibonacci heaps have large constant factors and complex implementations. They are rarely used in practice outside theoretical algorithm analysis. For most real applications, binary or 4-ary heaps with lazy deletion outperform them. The Fibonacci heap's theoretical importance is in proving asymptotic bounds.

# Conceptual pseudocode — Fibonacci heap operations
# (Full implementation is ~300 lines; this shows the key ideas)

# INSERT: simply add a new single-node tree to the root list
fn fib_insert(H, x):
    x.degree = 0; x.mark = false; x.child = null
    add x to H.root_list
    if x.key < H.min.key: H.min = x
    H.n += 1
    # Cost: O(1) — no consolidation!

# DECREASE-KEY: cut node, cascading cut if marked
fn fib_decrease_key(H, x, k):
    x.key = k
    if x.parent != null and x.key < x.parent.key:
        cut(H, x, x.parent)       # remove x from parent
        cascading_cut(H, x.parent) # propagate cuts upward
    if x.key < H.min.key: H.min = x
    # Cost: O(1) amortized — only O(1) cuts on average