Binary Heap & Priority Queue

What is a heap?

A binary heap is a binary tree with two rules:

1. Shape rule — complete tree: every level is full except possibly the last, which is filled from left to right. No gaps.
2. Order rule — heap property: in a min-heap, every parent is smaller than or equal to its children. (In a max-heap it’s the opposite.)

Because of rule 2, the smallest value is always at the root. That makes heaps perfect for “always give me the most urgent thing next”.

Analogy: a hospital emergency room. Patients don’t leave in arrival order (that would be a queue) — the most serious case is always treated next. That is a priority queue, and heaps are how we build one.

The magic trick: a tree inside an array

Because the tree is complete (no gaps), we can store it in a plain array, level by level, with no pointers at all:

The 3D model shows both views at once: the tree on top and the array in front. Every swap happens in both — they are the same data.

Insert — “bubble up”

1. Put the new value at the end of the array (the next free spot in the bottom level). The shape rule still holds.
2. While the value is smaller than its parent, swap it with the parent.

Each swap moves it one level up, and a heap with n items has about log₂ n levels, so insert is O(log n).

Extract-min — “sift down”

1. The minimum is the root, heap[0]. Save it.
2. Move the last element into the root and shrink the array. (Shape rule OK, order rule probably broken.)
3. While the moved value is bigger than its smaller child, swap it with that smaller child.

Again at most one swap per level: O(log n).

Code

class MinHeap:
    def __init__(self):
        self.a = []

    def insert(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0:
            p = (i - 1) // 2
            if a[i] >= a[p]:
                break
            a[i], a[p] = a[p], a[i]      # bubble up
            i = p

    def extract_min(self):
        a = self.a
        if not a:
            raise IndexError("heap is empty")
        smallest = a[0]
        last = a.pop()
        if a:
            a[0] = last
            i = 0
            while True:
                l, r = 2 * i + 1, 2 * i + 2
                c = i
                if l < len(a) and a[l] < a[c]: c = l
                if r < len(a) and a[r] < a[c]: c = r
                if c == i:
                    break
                a[i], a[c] = a[c], a[i]  # sift down
                i = c
        return smallest

h = MinHeap()
for v in [8, 15, 10, 30, 20, 1]:
    h.insert(v)
print([h.extract_min() for _ in range(6)])   # [1, 8, 10, 15, 20, 30]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    // C++ has a ready-made heap: priority_queue (a max-heap by default).
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int v : {8, 15, 10, 30, 20, 1}) minHeap.push(v);   // O(log n) each

    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";   // O(1) peek
        minHeap.pop();                  // O(log n) extract
    }
    // Output: 1 8 10 15 20 30
}

In Python the built-in module heapq turns a list into a min-heap: heapq.heappush(a, x) and heapq.heappop(a).

Heap sort

Extracting the minimum n times gives the values in sorted order — that is heap sort, an O(n log n) sorting algorithm that needs no extra array. Try pressing Extract min repeatedly in the model and write down the values.

Where are heaps used?

• Priority queues: CPU process scheduling, hospital triage, event simulations.
• Dijkstra’s shortest path and Prim’s MST — always pick the closest unvisited node.
• Top-k problems: “the 10 largest numbers in a stream of a billion”.
• Merging k sorted lists (e.g. in external sorting).

Common mistakes

• Thinking a heap is sorted. Only parent ≤ child is guaranteed; siblings are unordered.
• Off-by-one errors with 1-based formulas (2i, 2i+1) vs 0-based ones (2i+1, 2i+2).
• Swapping with the larger child during sift-down in a min-heap — always pick the smaller.