What is a heap?
A heap is a way to keep a collection so that the smallest item is always first. A new item can be added quickly. It is the usual way to build a priority queue.
A build system uses one to decide which job runs next, and an operating system uses one to decide which process gets the processor.
By the end of this lesson
Note
I can keep the smallest item at hand with a heap.
Key words
| Word | What it means |
|---|---|
| Heap | a tree where every parent is no bigger than its children |
| Priority queue | a queue where the most urgent item leaves first |
| Parent | the node directly above a node |
| Sift up | swap a new item with its parent until the rule holds |
| Sift down | swap an item with its smaller child until the rule holds |
| Min-heap | a heap with the smallest item at the top |
The cells students fill in are left blank in this preview.
A priority queue serves urgent items first
A normal queue serves the oldest item first. A priority queue serves the most urgent item first, whenever it arrived.
A hospital works this way. A patient with a broken leg waits behind one with a heart attack, even if they came in earlier. Here a smaller number means more urgent.
A heap keeps the smallest item on top
A min-heap is a tree with one rule: every parent is no bigger than its children. So the smallest item is always the root.
Siblings are in no order. The tree is stored in a plain list, level by level. The parent of index i is at (i - 1) // 2, and its children are at 2 * i + 1 and 2 * i + 2.
Worked example: a heap stored in a list
| Index | Item | Parent index | Children indexes |
|---|---|---|---|
| 0 | 2 | None | 1 and 2 |
| 1 | 5 | 0 | 3 and 4 |
| 2 | 4 | 0 | 5 and 6, not there |
| 3 | 9 | 1 | None |
| 4 | 7 | 1 | None |
The cells students fill in are left blank in this preview.
Make a heap and look at the top
python3 -c "import heapq; h = [5, 1, 4]; heapq.heapify(h); print(h[0]); print(heapq.heappop(h)); print(h)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Pushing adds at the end and sifts up
To push, add the item at the end of the list. Then compare it with its parent. If the parent is bigger, swap them, and compare again one level up.
Stop when the parent is smaller or the item reaches the top. The item rises at most one step per level, so the cost is the height of the tree.
Worked example: push 1 onto a heap
| Step | List | What happened |
|---|---|---|
| Add | 2 5 4 9 7 1 | 1 is at index 5; its parent is index 2, which holds 4 |
| Swap | 2 5 1 9 7 4 | 1 is at index 2; its parent is index 0, which holds 2 |
| Swap | 1 5 2 9 7 4 | 1 is at the top: stop |
The cells students fill in are left blank in this preview.
Watch a push sift up
# Push into a min-heap stored in a list, and show each swap.
heap = [2, 5, 4, 9, 7]
heap.append(1)
i = len(heap) - 1
while i > 0 and heap[(i - 1) // 2] > heap[i]:
parent = (i - 1) // 2
temp = heap[parent]
heap[parent] = heap[i]
heap[i] = temp
print("swap with parent at", parent, "->", heap)
i = parent
print(heap)
# Change the 1 in heap.append(1) to 6 and run again.
A common mistake
Warning
Many people think a heap keeps all its items in sorted order. It does not. It guarantees only that each parent is no bigger than its children, so only the top is certain. That is why a heap is cheaper to keep than a sorted list.
Popping takes the top and sifts down
To pop, take the item at index 0. Move the last item to the top to fill the gap.
Then compare it with its two children. If one is smaller, swap it with the smaller child, and repeat one level down. Stop when neither child is smaller.
Worked example: pop from a heap
| Step | List | What happened |
|---|---|---|
| Take | (1 is returned) 5 2 9 7 4 | The top is removed |
| Fill | 4 5 2 9 7 | The last item, 4, moves to the top |
| Swap | 2 5 4 9 7 | The children are 5 and 2; 2 is smaller, so swap with 2 |
| Stop | 2 5 4 9 7 | The children of index 2 are not there |
The cells students fill in are left blank in this preview.
The two smallest of four numbers
python3 -c "import heapq; print(heapq.nsmallest(2, [9, 4, 7, 1]))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.