Heaps

How a priority queue serves the most urgent job without sorting

A heap is a binary tree with one rule: every parent is smaller than or equal to its children. This version is called a min-heap. Because of the rule, the smallest item always sits at the top (the root), so you can read it in O(1) time.

Unlike ordered binary trees, a heap ignores how two siblings compare. For example, 2 on top with children 5 and 3, and 9 and 7 under the 5, is a valid heap: 2 leads, yet nothing is sorted. That looser rule keeps updates cheap.

A heap fills each level left to right before starting the next. A tree with no gaps like this is called complete, so it fits in a plain array with no pointers: the root goes at index 0, and the levels follow one after another.

Heaps

Python's heapq finds the top 10 of a million scores without sorting

Python's heapq.nlargest(10, scores) keeps a min-heap of the 10 best scores so far. Its root is the weakest of the ten, so each new score needs one comparison: if bigger, it replaces the root and sinks into place.

That costs O(n log k), with k = 10 here, instead of O(n log n) to sort all n scores. Java's PriorityQueue is also a binary heap, and Dijkstra's shortest-path algorithm uses one to pick the nearest unvisited place next.

Heaps

Each change only repairs one path from the top to the bottom

To add, put the item at the array's end and swap it with its parent while it's smaller. To remove the smallest, move the last item to the root and swap it with its smaller child until both children are bigger.

Each swap fixes one parent and child, so only one top-to-bottom path is touched. A complete tree of n items is about log₂ n levels tall, so both cost O(log n): at most about 20 swaps for 1,000,000 items.