When you always need the SMALLEST (or largest) thing next — the most urgent task, the closest node — a heap keeps it at your fingertips. It’s a tree where every parent is smaller than its children, so the minimum is always the root. Add or remove and it repairs itself in O(log n) by bubbling. It powers priority queues, Dijkstra, and heap-sort. Slide to pull the minimum off, again and again.
A binary heap is a complete binary tree (stored compactly in an array: node i’s children at 2i+1, 2i+2) satisfying the HEAP PROPERTY — every parent ≤ its children (min-heap). So the minimum is always the ROOT, found in O(1). Insert appends and BUBBLES UP; extract-min removes the root, moves the last element up, and SIFTS DOWN — both O(log n). Repeatedly extracting yields sorted order (heap-sort, O(n log n)). It is the standard priority queue behind Dijkstra, A*, and scheduling. A fail-loud self-check throws unless repeated extract-min emits keys in sorted order. ◆ real data structures, node-verified.
A binary min-heap is shown; it gives fast min + insert but NOT fast arbitrary search (that’s O(n)). The heap property and O(log n) sift are exact. Fibonacci heaps improve some bounds amortized.