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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Interval Overlap, Meeting Rooms, and End-Time Heaps.
Least You Need to Know: Interval Overlap, Meeting Rooms, and End-Time HeapsRelated lessons
Keep going with nearby lessons in the same topic.