Heap Algorithms
A tree kept just ordered enough that the best element is always at 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
1 is smaller than its parent 7, so they swap.
In this order
- Sift UpCompare with the parent and swap while the value outranks it. One path, O(log n).
- Heap InsertDrop the value in the next free slot, then let it climb until its parent outranks it.
- Sift DownSwap with the better child while a child outranks the value. One path, O(log n).
- Extract Min / MaxTake the root, move the last leaf up into it, then let that value sink.
- Heapify (Build Heap)Sift every parent down, last one first. The whole build costs O(n), not O(n log n).
- K-th Largest / SmallestKeep a min heap of size k; the root is the k-th largest after scanning everything.
- Binomial Heap MergeMerge two heaps by linking trees of equal degree like binary addition.
- Fibonacci Heap Decrease-KeyCut the node to the root list; cascading cuts keep the potential bounded.
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.
Or a different category
Sorting
You need every element in order, rather than repeated access to the current best one.
Tree Algorithms
You look elements up by key, or want the ones between two bounds, not just the extreme.