Heap sort

Heap sort is selection sort with a better way to find the largest value. It keeps the unsorted values in a heap, a tree stored inside the list itself, where the largest value is always at the top. Taking it off and repairing the heap takes about log n steps instead of a full scan.

A heap drawn as a binary tree above the same values as bars, the largest value at the root swapping to the end of the list
A heap drawn as a binary tree above the same values as bars, the largest value at the root swapping to the end of the list

A tree inside a list

A binary heap is a tree that needs no pointers. Place 0 is the root, and the children of place i are places 2i + 1 and 2i + 2, so place 1 and 2 are the children of the root, places 3 to 6 the next level, and so on. Every level is full except the last, which fills from the left. In a max-heap every parent is at least as large as its children, so the largest value is always at the root.

Sifting down

One operation does all the work. To sift a value down, compare it with its children. If the larger child is larger than the value, they swap, and the value is compared with its new children. It stops when no child is larger, or when it reaches the bottom. Because the tree has only about log₂ n levels, a sift-down takes at most about 2 log₂ n comparisons.

Building the heap, then sorting

To build the heap, sift down every parent, from the last one back to the root. Each subtree is a heap before its parent sifts down into it. Then sort: swap the root, the largest value, with the last value of the heap. That value is now in its final place. The heap is one shorter, and the value that landed at the root sifts down to repair it. Repeat until one value is left.

An example

Take 5, 1, 4, 2, 8. Building the heap sifts 1 down below 8, then 5 down below 8, which gives 8, 5, 4, 2, 1. Now 8 swaps to the end; 1 lands at the root and sifts down past 5 and 2: 5, 2, 4, 1 | 8. Then 5 goes to the end and 1 sifts down past 4: 4, 2, 1 | 5, 8. Two more rounds finish the list: 1, 2, 4, 5, 8, after 12 comparisons and 10 swaps.

Strengths and weaknesses

Heap sort takes time proportional to n log n even in the worst case, and it needs no extra memory. Quicksort can slow down to n² and merge sort needs a buffer as long as the list, so heap sort is the safe fallback: introsort, used by the C++ standard library, switches to it when quicksort's partitions go wrong. On real computers it is usually slower than both, because it jumps between distant places in the list, and it is not stable. J. W. J. Williams published heap sort, together with the binary heap, in 1964.

Explore it

Open the app and press Step. The tree above the bars shows the heap: the value sifting down has its own colour, the child it is compared with is highlighted, and every swap shows in both the tree and the bars. Once the heap is built, watch the root swap to the end, turn green, and drop out of the tree.

Frequently asked questions

What is the time complexity of heap sort?

O(n log n) in the best, average and worst case. Building the heap takes O(n), and each of the n − 1 extractions takes O(log n). It sorts in place with O(1) extra memory.

What is the difference between heap sort and selection sort?

Both take the largest (or smallest) remaining value again and again. Selection sort finds it with a full scan of the unsorted part, n comparisons each time. Heap sort keeps the unsorted part in a heap, where the largest value is already at the top, and repairing the heap costs only about log n comparisons.

What is a heap used for besides sorting?

Priority queues: a heap gives the largest (or smallest) item at once and lets you add or remove items in about log n steps. Schedulers, Dijkstra's shortest-path algorithm and event simulations all use one.

Is heap sort stable?

No. Swapping the root to the end moves values over long distances, so equal values can change their order.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try heap sort