Heaps

Min-heap order, the array layout, and priority queues.

The idea

A heap is the standard structure behind a priority queue: a collection that supports three operations — insert an item, read the smallest item, and remove the smallest item. A sorted list answers the last two at once but pays for every insertion; an unsorted list inserts at once but pays for every lookup. A heap keeps all three operations cheap.

A min-heap is a binary tree — every node has at most two children — satisfying the heap order: the value at each node is $\le$ the values at its children. The order constrains only parent-to-child links; siblings are not compared. Along any path down from the root the values never decrease, so the root holds the minimum of the entire tree, and reading it takes a single step.

Insertion and removal repair the order locally, each leaving exactly one value out of position and walking it into place.

Algorithm.

Algorithm: Insert Input: a heap, a new value v Output: the heap with v added 1. place v in the first free position on the bottom level // keeps the tree's shape 2. if v is smaller than its parent, swap the two and go to step 2 // sift up 3. return the heap // heap order holds again

Algorithm.

Algorithm: Extract-min Input: a nonempty heap Output: its smallest value, removed from the heap 1. remove the root and save it // the root is the minimum 2. move the last value of the bottom level into the root's place; call it v 3. if v is larger than a child, swap v with its smaller child and go to step 3 // sift down 4. return the saved value // heap order holds again

Each swap moves the out-of-place value one level, so both operations are bounded by the tree's height, the number of levels.

Ways to work on it

• Walkthrough. The min-heap property, peek, and extract-min.
• Practice. Find the min or validate the heap property.
• Hardest. Array layout and an insert via sift-up.

Not sure where to start? Take the ten-question placement test.