Heaps & Priority Queues
Think of it like this
Imagine an emergency room where patients aren't treated in arrival order, the most critically ill patient is always treated first. That's a priority queue: each element has a priority, and the highest-priority element is always at the front.
A heap is the data structure that implements a priority queue efficiently. It's a complete binary tree with one rule: the parent is always ≥ its children (max-heap) or always ≤ its children (min-heap).
Max-Heap: 90 Rule: parent ≥ both children
/ \ Root = always the maximum
75 82
/ \ / \
55 60 71 45
Min-Heap: 5 Rule: parent ≤ both children
/ \ Root = always the minimum
12 8
/ \ / \
20 15 10 11The Array Trick
A complete binary tree can be stored perfectly in an array with no wasted space and no pointers. The index relationships are: