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 task

Implement MinHeap::push, MinHeap::pop (assume non-empty) and top.

Challenge 2

Write void heapify(std::vector<int>& a), which turns any array into a min-heap in O(n): sift down every node that has children, starting from the last one (n / 2 - 1) and going back to the root. Also write bool is_min_heap(const std::vector<int>& a).

Challenge 3

Write RunningMedian: add(x) takes numbers one at a time, and median() returns the median of everything added so far. Keep the smaller half in a max-heap and the larger half in a min-heap (std::priority_queue), sized so they differ by at most one; the median is then on top. median() is only called after at least one add.

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