Heaps and
Priority Queues

Abstract interface

A priority queue is a container where each element has an associated priority. Core operations:

• insert(key, priority) — add an element with the given priority
• extract-min / extract-max — remove and return the highest-priority element
• peek-min / peek-max — return highest-priority element without removing
• decrease-key(handle, new_priority) — lower the priority of an existing element
• merge(pq1, pq2) — combine two priority queues into one

Implementations compared

* = amortised

Complete binary tree

A binary heap is a complete binary tree — every level is fully filled except possibly the last, which is filled left to right.

• Height is always O(log n) — guarantees worst-case operation bounds
• No wasted space in the array representation — no pointers needed
• Cache-friendly contiguous memory layout
• Predictable shape makes implementation simple

Min-heap property

Every node's key is less than or equal to both of its children's keys. The root holds the minimum.

Max-heap property

Every node's key is greater than or equal to both of its children's keys. The root holds the maximum.

Implicit tree in an array

A complete binary tree maps perfectly to a flat array with zero overhead — no pointers, no node allocations, no fragmented memory.

Navigation formulas (0-indexed)

Algorithm

1. Append the new element at the end of the array (next leaf position)
2. Compare with parent — if smaller (min-heap), swap
3. Repeat up the tree until heap property is restored or root is reached

def insert(heap, key):
    heap.append(key)
    i = len(heap) - 1
    # Sift up
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

Visual walkthrough — insert 1

Algorithm (extract-min)

1. Return the root element (the minimum)
2. Move the last element to the root position
3. Compare with children — swap with the smaller child
4. Repeat down the tree until heap property is restored or a leaf is reached

def extract_min(heap):
    minimum = heap[0]
    heap[0] = heap.pop()  # move last to root
    sift_down(heap, 0)
    return minimum

def sift_down(heap, i):
    n = len(heap)
    while 2 * i + 1 < n:
        child = 2 * i + 1
        if child + 1 < n and heap[child+1] < heap[child]:
            child += 1
        if heap[i] <= heap[child]:
            break
        heap[i], heap[child] = heap[child], heap[i]
        i = child

Visual walkthrough

Extract-min from [2, 5, 3, 8, 7, 9, 4]:

The naive approach

Insert elements one by one: n insertions × O(log n) each = O(n log n).

Floyd's algorithm (bottom-up)

Start from the last internal node and sift-down each node, working backwards to the root.

def build_heap(arr):
    n = len(arr)
    # Start from last internal node
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

Work distribution by level

Half the nodes are leaves (zero work), a quarter do one swap, an eighth do two — the geometric series converges to O(n).

Summing the work

T(n) = Σ (k=0 to h) ⌊n / 2^(k+1)⌋ · k

     = n · Σ (k=0 to ∞) k / 2^(k+1)

     = n · Σ (k=0 to ∞) k · x^k   where x = 1/2

The key identity

Using the power series identity Σ k·x^k = x / (1-x)² for |x| < 1:

Σ (k=0 to ∞) k / 2^k = (1/2) / (1 - 1/2)²
                       = (1/2) / (1/4)
                       = 2

Therefore: T(n) = n · 2 / 2 = n

Build-heap is O(n)

This is a tight bound — you cannot build a heap faster than O(n) because you must at least read every element.

Algorithm

1. Build a max-heap from the input array — O(n)
2. Repeatedly extract the maximum and place it at the end:

def heap_sort(arr):
    n = len(arr)
    # Phase 1: build max-heap -- O(n)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

    # Phase 2: extract max -- O(n log n)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, 0, end)

Properties

Structural difference

Converting between them

Negate all keys: a min-heap on -key behaves as a max-heap on key.

# Max-heap via Python's heapq (min-heap):
import heapq
max_heap = []
heapq.heappush(max_heap, -value)
largest = -heapq.heappop(max_heap)

Language defaults

Generalising the branching factor

A d-ary heap is a complete d-ary tree satisfying the heap property. A binary heap is the special case d = 2.

Navigation (0-indexed)

Trade-offs

4-ary heap example

Binomial trees

A binomial tree B_k is defined recursively:

• B_0 is a single node
• B_k is formed by linking two B_(k-1) trees — one becomes the leftmost child of the other's root
• B_k has exactly 2^k nodes and height k

Binomial heap structure

A collection of binomial trees where:

• Each tree satisfies the min-heap property
• At most one tree of each order (like binary representation of n)
• Trees stored in a linked list sorted by order

Lazy mergeable heap

A Fibonacci heap is a collection of heap-ordered trees with:

• A min pointer to the root with the smallest key
• Trees stored in a circular doubly-linked list of roots
• Each node tracks its degree and a mark bit

Key operations

• insert: create single-node tree, add to root list, update min — O(1)
• merge: concatenate root lists, update min — O(1)
• extract-min: remove min, add children to root list, consolidate — O(log n)*
• decrease-key: cut node, add to root list, cascade cuts — O(1)*

* = amortised

Structure diagram

Potential function

Define Φ = t + 2m where t = number of trees in root list, m = number of marked nodes.

Why O(log n) max degree?

• A node of degree k has at least F_(k+2) descendants
• F_(k+2) ≥ φ^k where φ = (1+√5)/2 ≈ 1.618
• Therefore k ≤ log_φ(n) = O(log n)

A simpler alternative

Pairing heaps achieve similar practical performance to Fibonacci heaps with a much simpler implementation. Each node stores:

• A key value
• A pointer to its leftmost child
• A pointer to its next sibling

Operations

* conjectured O(1), proven O(log log n) by Pettie 2005

Extract-min: two-pass pairing

1. Remove the root
2. Left-to-right pass: pair adjacent siblings, merge each pair
3. Right-to-left pass: merge resulting trees into one

The decrease-key problem

A standard binary heap cannot locate an arbitrary element — you can only access the root. Graph algorithms need to update priorities of elements already in the queue.

Solution: position maps

Augment a binary heap with an index table tracking where each element lives in the heap array:

Heap array:    [A:2, C:5, B:3, D:8, E:7]
Position map:  { A→0, B→2, C→1, D→3, E→4 }
Inverse map:   { 0→A, 1→C, 2→B, 3→D, 4→E }

Every swap in sift-up/sift-down must also update both maps — constant overhead per swap.

Operations

Shortest paths with a priority queue

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

    while not pq.is_empty():
        u = pq.extract_min()
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                pq.decrease_key(v, new_dist)
    return dist

Complexity depends on the heap

Key takeaways

• A priority queue is an ADT; a binary heap is its most common implementation
• Binary heaps use an implicit array — no pointers, O(1) space overhead
• Build-heap is O(n) via Floyd's bottom-up sift-down — not O(n log n)
• Heap sort is O(n log n) worst-case, in-place, but not stable
• Fibonacci heaps offer O(1) amortised decrease-key — optimal for dense-graph Dijkstra's
• Pairing heaps are simpler than Fibonacci heaps and often faster in practice
• Indexed priority queues solve the decrease-key lookup problem
• D-ary heaps (d=4) often beat binary heaps due to cache effects

Recommended reading