Interactive Data Structure Visualizations Heap Sort

Sorting algorithms are among the most fundamental algorithms of computer science. A sorting algorithm takes an array of data and rearranges it so that it is in ascending, or sometimes descending order according to some sort key.

In this animation of sorting the data consists of an array of integers--the integers themselves are the sort key. There are many different algorithms that can be used to sort an array. Some algorithms are conceptually very intuitive while others are more subtle. Among sorting algorithms, those that are most efficient tend to be the most subtle. The heap sort algorithm belongs to this category. The heap sort algorithm relies on the connection between an complete binary tree and the array of values that correspond to it. The values in the array at the bottom of the screen are the same values that are in the tree enumerated in level order.

The primary advantage of the heap sort is its efficiency. The execution time efficiency of the heap sort is O(n log n). The memory efficiency of the heap sort, unlike the other n log n sorts, is constant, O(1), because the heap sort algorithm is not recursive.

The heap sort algorithm has two major steps. The first major step involves transforming the complete tree into a heap. The second major step is to perform the actual sort by extracting the largest element from the root and transforming the remaining tree into a heap.

In this step, the complete tree is transformed into a heap. This process is accomplished by beginning at the top of the tree. Each subtree is transformed into a heap by an operation similar to the enqueue operation of a priority queue. When you watch the animation, notice that the nodes at the top of the tree turn from blue to red. As each subtree is transformed into a heap, the node that constitutes its root becomes red. The big-O of this transformation into a heap is O(n log n) because it is done on each of the nodes n, the reheaping process must travel down one branch of the tree (log n).

Once the tree has been transformed into a heap, the root node contains the largest value--a property that is true of all heaps. The root value is swapped with the value in the right-most node on the lowest level. As you watch the animation, notice that the later node turns back to blue. Also its value in the list at the bottom of the screen becomes blue. The blue nodes and values are those that are in sorted order. Excluding the right-most node at the bottom level from the tree, the remaining subtree is almost a heap. It is then changed back into a heap. This operation is similar to the dequeue operation of a priority queue. The big-O of the second step is O(n log n) because it must be performed on each node (n), the reheaping process being log n.