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. In a list with both, the numbers come first. 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 color 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 builds the heap from the bottom up, in linear time rather than one insertion at a time.
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 recolors a bar or two. The web's accessibility guidelines allow anything that flashes three flashes a second at most, and capping the animation at three steps a second keeps it well inside that. Step forward goes as fast as you can click.
Sources
- Wikipedia: Heapsort
- J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM 7(6), June 1964
- Robert W. Floyd, "Algorithm 245: Treesort", Communications of the ACM 7(12), December 1964
Added . Last updated and reviewed . What's new






