Using the visualizer
Type a list in the box, separated by commas, spaces or new lines. Numbers are sorted by value and words alphabetically, ignoring capitals. The sorted list appears straight away, and the animation below plays the sort one step at a time, up to 24 items.
Play, Step forward, Step back and Speed control the animation, and the key under the bars says what each colour means. Show the steps lists the heap being built and each item taken off it.
How heap sort works
A heap is a tree where every parent is at least as big as its children. It fits in a list without any extra space: the item at position i has its children at positions 2i + 1 and 2i + 2, counting from 0. So the biggest item in a heap is always at the front.
Heap sort first rearranges the list into a heap, pushing small parents down below their bigger children. Then it swaps the front item, the biggest, to the end, where it's in its final place. The new front item probably breaks the heap, so it sinks down again until the heap is fixed. Repeat, and the sorted part grows from the back.
Never slow, never stable
Heap sort makes on the order of n log n comparisons even in the worst case, which quick sort can't promise, and it sorts in place, which merge sort can't. The cost is that equal items can swap order, so it isn't stable.
Where it came from
J. W. J. Williams invented heapsort in 1964, and his paper introduced the binary heap as a useful structure in its own right. The same year, Robert W. Floyd published an improved version that sorts the list in place.
Questions
Where's the tree in the animation?
The heap is stored in the list itself, so the bars are the tree read row by row: the first bar is the top, the next two are its children, the next four their children, and so on.
What's a heap used for besides sorting?
Priority queues: anything that needs the biggest or smallest item quickly, again and again, such as a scheduler picking the next job.
Why does the animation only go up to 3 steps a second?
Each step recolours a bar or two, and three changes a second is the limit the web's accessibility guidelines set for anything that flashes. Step forward goes as fast as you can click.