Algorithms / Heap Invariants
Least You Need to Know: Heaps, Heap Invariants, and Fast Extremes
A heap stores items so the **root is always the minimum or maximum** according to a priority rule. It does not fully sort everything, but it lets you update the frontier quickly when you repeatedly need the next best element.
The least you need to know
- A heap is a complete binary tree stored compactly in an array.
- The heap property compares each node only with its children, not with every later element.
- Push and pop take logarithmic time because only one root-to-leaf path may need repair.
- A heap is ideal when you repeatedly need the smallest or largest current item.
- A heap is not the same as a fully sorted array.
Key notation
min-heap
smallest key at the root
max-heap
largest key at the root
sift up / sift down
restore heap property after insert or remove
Tiny worked example
- Put incoming tasks into a min-heap keyed by priority.
- The root is always the next task with the smallest key.
- After removing the root, move the last element to the top and sift down.
- Only one path changes, so the repair is logarithmic rather than linear.
Common mistakes
- Students often think a heap means the entire array is globally sorted.
- Students often forget that only parent-child order is guaranteed.
- Students often choose a heap when they only need one final sort and no repeated frontier updates.
How to recognize this kind of problem
- You repeatedly need the smallest or largest current element.
- Items are arriving, expiring, or being updated over time.
- A full sort each step would be wasteful.