A pile where the smallest item is always on top, and adding or removing stays fast.
In an emergency room the most urgent patient is seen first, no matter who arrived first. A priority queue does that. A min-heap is a clever way to build one: a tree where every parent is smaller than or equal to its children. So the smallest value always sits at the very top (the root), and you can grab it instantly.
The trick is that the tree is stored in a plain array, with no pointers. For the item at index i: its children are at 2i+1 and 2i+2, and its parent is at (i-1)/2. The two views below are the same data.
9, 7, 5, 3, 1 (biggest first). Each new item travels all the way to the top. Why?1, 2, 3, 4, 5 (smallest first). How many swaps now?heapify 9 8 7 6 5 4 3 2 1 and watch it fix the tree from the bottom up.h.a[0] panics with “index out of range”. Check the length first.2i+1 and 2i+2 for a 0-based array (they are 2i and 2i+1 in 1-based books).container/heap, which gives you Push/Pop with the same sift logic. This page shows what happens inside.O(1)). Push and pop move along one root-to-leaf path, so they take about log₂(n) steps (O(log n)): 1,000,000 items need only about 20 swaps. Heapify of a whole array takes only O(n).