Heap Algorithms
A tree kept just ordered enough that the best element is always at the root.
Binary Heap: Insert climbs to the root
A binary heap keeps one rule: every parent outranks its children. Not a full ordering, just that. A complete tree with that property has its best element at the root, so peek is O(1), and it is stored in a plain array where the children of index i sit at 2i + 1 and 2i + 2, so there are no pointers and no allocation per node.
Both operations that disturb the rule repair it along a single path. An insert drops the value into the next free slot and sifts it up while it outranks its parent. An extract takes the root, moves the last leaf into the hole, and sifts it down past the better of its two children. A complete tree of n nodes is log n deep, so each operation touches log n nodes rather than n.
Building a heap out of an array already in memory is the surprising part: sifting every parent down, starting from the last one, costs O(n) rather than O(n log n), because half the nodes are leaves with nowhere to sink and only the root can fall the full depth. That is what makes heap sort's setup free, and what makes a heap the structure for pulling the k best out of n.
After this you can
- Sift a value up and down, and say why each one touches a single path
- Insert into and extract from a heap and account for where the log n comes from
- Build a heap from an array in O(n) and explain why the bound is not n log n
- Keep a size-k heap to find the k-th largest of a stream in O(n log k) with O(k) memory
In this order
Where people go wrong
Expecting a heap to be sorted
Printing the backing array gives you the root first and then nothing you can rely on. Only the root is guaranteed. The second best is one of two children, and getting the whole order out means n extracts at log n each.
Building by repeated insert
Pushing n values one at a time costs O(n log n). Calling heapify on the same array costs O(n). If you already hold all the values, sift down from the last parent instead of pushing them in.
Changing a value that is already inside
A heap has no way to find an arbitrary element short of scanning all n slots, so decrease-key needs a side map from value to position, kept up to date on every swap. Without one, each update is O(n) and the log n bound is gone.