This page was made to interactively trace the heapsort algorithm.
The simplest way to understand how heapsort works is to think of it as an extension of
selection sort.
Selection sort
works by building a sequence through repeatedly removing the minimum from the input list.
Take the following example to see selection sort turn an unsorted list into a sorted one:
Unsorted Input
Sorted Output
87 23 90 12 34
87 23 90 34
12
87 90 34
12 23
87 90
12 23 34
90
12 23 34 87
12 23 34 87 90
The heapsort algorithm works very much like the selection sort algorithm explained above but with a slight difference.
The unsorted list in heapsort is a heap. This makes it possible to
remove each minimum value in O(log n) time instead of O(n) time
from the unsorted list in selection sort. The
improvement in removal efficiency helps heapsort get an overal efficiency of O(n log n).
The algorithm follows the following main 2 steps:
Heapify/build the heap.
+
This would take O(n log n) time. Each insertion takes O(log n) time and there are n insertions.
Repeatedly remove the top off the heap.
+
The sorted list is made by the order of removal.
The top is always going to be either a maximum or minimum depending on whether the heap is "Max-top" or "Min-top".
By repeatedly removing the top, we end up removing in sorted order.
This would take O(n log n) time. Each removal takes O(log n) time and there are n deletions.
Use the following components to trace the algorithm and view the contents of the heap at each step.