Skip to content
All apps

Heapsort

About this app

Heapsort step by step — build the heap, restore the heap property and sort step by step.

How Heapsort works

Heapsort uses a max-heap: a complete binary tree in which every parent is at least as large as its children. The tree lives directly in the array; the children of position i are at 2i+1 and 2i+2. First the array is turned into a heap by sifting down every node from the last inner position backwards. Then the maximum sits at the root. It is swapped with the last element of the heap, the heap shrinks by one and the new root sifts down until the heap property holds again. This repeats until everything is sorted. Running time: O(n log n) in every case.

What the app shows

The binary tree is at the top and the same array as a list below it. The root, the node that is sifting down and the parent–child pair being compared or swapped are highlighted. The sorted region grows at the back of the array. A phase indicator separates building, sorting and done, a counter shows the heap size and the number of sorted elements, and a text explains each step.

Try it yourself

Enter your own numbers and step forwards and backwards or let it play. Watch how after every swap the largest remaining element rises to the root again, and how the tree and the array always show the same thing. A list sorted in descending order is a good test: it already is a max-heap, so building the heap needs not a single swap.

Frequently asked questions

What is a max-heap?
A max-heap is a complete binary tree in which every node is at least as large as its children, so the largest element is always at the root. It is usually stored as an array: the children of index i are at 2i+1 and 2i+2, the parent at (i−1)/2 rounded down.
What does sift down mean?
A node that is smaller than one of its children is swapped with the larger child and keeps moving down until it is greater than or equal to both children or reaches a leaf. This restores the heap property in O(log n) steps.
What is the time complexity of Heapsort?
Heapsort takes O(n log n) in the best, average and worst case and sorts in place without extra memory. Building the heap alone costs only O(n). Heapsort is not stable.
What does the Heapsort app show?
The tree and the array side by side, with the root, the sifting node and the compared pair highlighted. You enter your own numbers, go through every step and watch the sorted region grow at the back of the array.

Subject: Computer science

More from Computer science

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps