Lesson 25 — Ultimate: build a min-heap

Boss level: a heap from scratch

A min-heap is a binary tree stored in a plain list: the children of index i are at 2i + 1 and 2i + 2, and its parent is at (i − 1) // 2. The rule: every parent is ≤ its children, so the smallest item is always at index 0. Push: add at the end, then sift up — swap with the parent while the parent is bigger. Pop: take index 0, move the last item to the top, then sift down.

parent = (i - 1) // 2

Why it matters: this is exactly what heapq does inside; now you know why push and pop cost only O(log n).