Heap as Array Arithmetic

The heap property

A min-heap is a binary tree where every node's value is less than or equal to its children's values. Equivalently, the smallest element is at the root. (Max-heap: every node ≥ its children; largest at root.) The tree is also "complete", all levels filled except possibly the last, which fills left to right.

The completeness constraint is what makes the array representation work. A complete binary tree maps naturally to a contiguous array: level by level, left to right. Index 0 is the root; indices 1 and 2 are its children; indices 3, 4 are grandchildren via the left child; indices 5, 6 are grandchildren via the right child; and so on.

Index arithmetic

Given a node at index i in a 0-indexed heap:

• Left child: 2i + 1
• Right child: 2i + 2
• Parent: (i − 1) / 2 (integer division)

Some textbooks use 1-indexing because the formulas are even cleaner: parent at i / 2, children at 2i and 2i + 1. Either choice works; pick one and stick with it.

Push and pop

Push: append to the end of the array, then "sift up", repeatedly swap with the parent if the heap property is violated. The path from the new node to the root has length O(log n); each swap is O(1). Total: O(log n).

Pop (remove the min/max): the root holds the answer. Move the last element of the array to the root, decrement size, then "sift down", repeatedly swap with the smaller child if the heap property is violated. Same depth, same constant work per level. Total: O(log n).

# Min-heap from scratch
class MinHeap:
    def __init__(self):
        self.h = []

    def push(self, x):
        self.h.append(x)
        self._sift_up(len(self.h) - 1)

    def pop(self):
        if not self.h: raise IndexError
        top = self.h[0]
        last = self.h.pop()
        if self.h:
            self.h[0] = last
            self._sift_down(0)
        return top

    def _sift_up(self, i):
        while i > 0:
            p = (i - 1) // 2
            if self.h[i] < self.h[p]:
                self.h[i], self.h[p] = self.h[p], self.h[i]
                i = p
            else:
                return

    def _sift_down(self, i):
        n = len(self.h)
        while True:
            l, r = 2*i+1, 2*i+2
            smallest = i
            if l < n and self.h[l] < self.h[smallest]: smallest = l
            if r < n and self.h[r] < self.h[smallest]: smallest = r
            if smallest == i: return
            self.h[i], self.h[smallest] = self.h[smallest], self.h[i]
            i = smallest

In production: use the language's heap (Python's heapq, C++'s priority_queue, Java's PriorityQueue). Implementing one yourself is a useful exercise but standard libraries are faster and have edge cases (custom comparators, concurrent access) you don't want to reinvent.

Heapify in O(n), the proof

Building a heap from an unordered n-element array could be done by n pushes. O(n log n). But there's a faster way: process elements bottom-up, sifting each one down. The argument that this runs in O(n) is one of the prettier results in the field.

def heapify(h):
    n = len(h)
    for i in range(n // 2 - 1, -1, -1):     # last non-leaf to root
        sift_down(h, i, n)

The key insight: in a complete binary tree of n nodes, half the nodes are leaves (which sift down by 0), a quarter are at depth 1 (sift down by at most 1), an eighth are at depth 2 (sift down by at most 2), and so on. The total work is bounded by:

sum over levels k from 0 to log n of (n / 2^(k+1)) × k
= n × sum over k of k / 2^(k+1)
= n × (1/2 × sum of k / 2^k)
= n × (1/2 × 2)        [the sum k/2^k converges to 2]
= n

So heapify is O(n). This is genuinely surprising the first time you see it, most algorithm-construction processes are at least n log n.

When heaps beat BSTs

• You only need the min or max. Heap: O(log n) push, O(log n) pop, O(1) peek. BST: O(log n) for everything but with much higher constant factors.
• Memory is contiguous. Cache-friendly access; no per-node allocation.
• You don't need ordered iteration. A heap's iteration order is arbitrary, only the root is special. A BST iterates in sorted order.
• You don't need range queries. "Give me all values between A and B" is O(log n + k) on a BST and O(n) on a heap.

Reach for a heap when you have a priority queue. Reach for a BST when ordered access matters.

Where heaps appear

• Heapsort. Heapify in O(n), then n pops in O(log n) each. O(n log n) total. In-place; no extra memory beyond the input array.
• Dijkstra's algorithm. The priority queue holds (distance, node) pairs; pop the smallest distance, relax its neighbours.
• Top-K with bounded score-range (heap-of-K. O(n log k)) see Top K Frequent Elements.
• Median from a stream. Two heaps, a max-heap of the lower half and a min-heap of the upper half. The median is at one of the two roots.
• Merging K sorted lists. Heap holds the head of each list. Pop the smallest; push its successor.

Where beginners go wrong

• Off-by-one between 0- and 1-indexing. Pick a convention. Don't mix. Most textbooks use 1-indexing; most programming-language libraries use 0-indexing. Both work; mixing them means parent of index 1 is computed as (1−1)/2 = 0 in 0-indexed and 1/2 = 0 in 1-indexed, both happen to land at the right place, but the children formulas diverge dramatically.
• Heapifying from the top down. Sifting down from index 0 first leaves the deeper subtree's invariants broken. Always heapify from the last non-leaf upward.
• Using a heap when you wanted a sorted iterator. Heap's iteration is unordered. If you need sorted access, use a BST or a sorted container.
• Re-implementing instead of using heapq. Python's heapq is implemented in C and significantly faster than any pure-Python heap. Write your own only as an exercise.
• Storing tuples and forgetting tie-breaking. Python heaps compare tuples element-wise. (priority, item) with non-comparable items will crash on a tie. Add a unique counter as a tiebreaker: (priority, counter, item).

What to read next

The Trees module covers BSTs and tries as the comparison points. The Sorting & Search module covers heapsort. Graphs covers Dijkstra, where the heap-as-priority-queue earns its keep.