Heaps & priority queues

A queue serves items in the order they arrived. A priority queue serves them by priority instead: you can add an item at any time, and taking one out always gives the smallest (or, if you choose, the largest) of those still waiting. Think of a hospital's waiting list, a timer system running whichever timer is due soonest, or a search that always extends its cheapest path so far.

The obvious ways to build one are each slow at one of the two operations:

A heap keeps the list only partly in order: enough to know the smallest item, and cheap to repair after each change.

A complete binary tree is a binary tree where every level is full except possibly the last, and the last level is filled from the left. Such a tree needs no references at all: number the nodes level by level, left to right, and store them in a list in that order. For the item at index i, the children are at 2i + 1 and 2i + 2, and the parent is at floor((i − 1) / 2).

A binary heap is a complete binary tree with one more rule, the heap property. In a min-heap, every parent is no larger than its children, so the smallest value is always the root, heap[0]. A max-heap is the mirror image: every parent is no smaller than its children, and the largest value is at the root.

So a heap is not sorted. In the min-heap [1, 3, 6, 5, 9, 8, 7], 6 sits above 8 and 7, but 5, which is smaller, sits on a lower level of the other branch. Each change only has to repair one path between the root and the bottom, and the tree has about log₂ n levels.

Appending keeps the tree complete, but the new value may be smaller than its parent. Swap it with its parent while that is so. This is called sift up. It stops at the first parent that is no larger, or at the root.

The smallest item is the root, but removing it leaves a hole at the top. Fill it with the last item, which keeps the tree complete, and then repair the order: while the moved item is larger than one of its children, swap it with the smaller child. That is sift down. Choosing the smaller child matters: it is the only one that can sit above the other child.

Pushing n items one by one costs O(n log n). Heapify does better: start from the list as it is, and sift down every item that has children, from the last such item back to the root. Each sift down only has to fix one subtree, and the subtrees below it are already heaps by then.

Half the items are at the bottom and never move, a quarter can sink at most one level, an eighth at most two, and so on. Adding that up gives fewer than n swaps in total: heapify is O(n).

The walkthrough heapifies a list of stone piles into a max-heap, then plays a game that needs the largest value over and over: halve the biggest pile, k times. Each turn shrinks the root in place and sifts it down, one O(log n) step instead of a pop and a push.

Library heaps can't change an item's priority in place. The usual workaround is to push the item again with its new priority and, when an outdated copy comes out of the heap later, skip it.

Heapify a list into a max-heap and pop everything, putting each popped item in the slot freed at the end, and the list ends up sorted. That is heap sort: O(n log n) in the worst case and in place, but not stable, and in practice usually slower than quicksort.