Step 5 of 6

A binary heap by hand

A binary heap is a tree with a clever trick: it's stored in a plain array, with no pointers at all. The tree is always complete (every level full except possibly the last, which fills from the left), so the nodes can be numbered level by level, and the parent/child links are just arithmetic:

index:    0   1   2   3   4   5
parent(i) = (i - 1) / 2      children(i) = 2i + 1, 2i + 2

           2                a = [2, 5, 3, 9, 6, 4]
         /   \
        5     3             children of index 1 (the 5): indexes 3 and 4 (9 and 6)
       / \   /              parent of index 5 (the 4): index 2 (the 3)
      9   6 4

In a min-heap, every parent is ≤ its children, so the minimum is always at index 0. (The tree is not sorted beyond that: 9 and 4 are on different branches, in no particular order.)

• push: append at the end, then sift up: swap with the parent while smaller.
• pop: move the last element to the root, then sift down: swap with the smaller child while larger.

Here's sift up, printed step by step:

#include <iostream>
#include <utility>
#include <vector>

void print(const std::vector<int>& a) {
    for (int x : a) std::cout << x << " ";
    std::cout << "\n";
}

int main() {
    std::vector<int> a = {2, 5, 3, 9, 6, 4};
    a.push_back(1);                             // new element at index 6
    print(a);
    std::size_t i = a.size() - 1;
    while (i > 0 && a[i] < a[(i - 1) / 2]) {    // smaller than its parent?
        std::swap(a[i], a[(i - 1) / 2]);
        i = (i - 1) / 2;
        print(a);
    }
    std::cout << "min is " << a[0] << "\n";
}

2 5 3 9 6 4 1 
2 5 1 9 6 4 3 
1 5 2 9 6 4 3 
min is 1

Why it's O(log n)

A complete tree with n nodes has about log₂ n levels. Sift up moves one level per swap, and so does sift down, so both operations do at most log n swaps. This is exactly what's inside std::priority_queue.

Sift down for pop

After moving the last element to index 0 (and removing the last slot), repeat: find the smaller of the node's children (check that each child index is < size); if it's smaller than the node, swap and continue from there; otherwise stop. Swapping with the smaller child is what keeps the heap rule true for both branches.

Your turn: implement MinHeap::push, MinHeap::pop (assume non-empty) and top.

Previous: Level order with a queue Next: Challenge: a trie for autocomplete