Sometimes you don't need everything sorted, just the most important item next: the patient who's most urgent, the task due soonest, the closest unexplored place on a map. That's a priority queue, and the usual way to build one is a heap.
A min-heap is a binary tree with one rule: every node is smaller than (or equal to) its children. So the smallest value is always at the root, ready to take. The tree is kept complete (filled level by level, left to right), which means it fits neatly in an array: the children of index i are at 2i + 1 and 2i + 2.
To add a value, put it at the end and let it bubble up, swapping with its parent while it's smaller. To take the smallest, remove the root, move the last value to the top, and let it sink down past its smaller child. Either way only one path from top to bottom is touched, so a heap of a million items needs about 20 swaps.
Python has this built in as heapq, which keeps a plain list in heap order.
import heapq
tasks = []
heapq.heappush(tasks, (3, "tidy desk"))
heapq.heappush(tasks, (1, "fix outage"))
heapq.heappush(tasks, (2, "reply to email"))
print(heapq.heappop(tasks))
print(heapq.heappop(tasks)[1])(1, 'fix outage') reply to email
A max-heap is the same with the rule flipped. A trick in Python: push negative numbers into heapq to get the biggest first.
Where is the smallest value in a min-heap?
| Priority queue | Take out the most important item next. |
|---|---|
| Min-heap | Each parent ≤ its children; smallest at the root. |
| In an array | Children of i at 2i + 1 and 2i + 2; parent at (i - 1) // 2. |
| heapq | Python: heappush(), heappop(), heapify(). |