Heapsort

Heapsort is a type of selection sort that sorts N items in O(N lg N) time (worst case) using comparisons. It first converts the input sequence into a a tree that satisfies the heap property—each node's value is less than or equal to that of its parent. Such trees are appropriately enough called heaps. As a result of the heap property, the largest element in the tree will be at the root. The algorithm repeatedly removes the largest element, replaces it with another value from the bottom level of the tree, and then re-establishes the heap property, thus forming the sorted array from the largest to the smallest element.

In order to do all of this quickly, we represent the tree as a complete binary tree—each level of the tree is completely full, with the possible exception of the lowest level, all of whose nodes are located as far to the left of the level as possible. Such trees have the nice property that we can store them sequentially in an array using a simple rule to find the children and parent of a node: the parent of the node at index k>0 in the array is at index ⌊(k-1)/2⌋. Likewise, the children of node k, if present, are at indices 2k+1 and 2k+2. The rightmost node on the last level of the tree is therefore the last element of the array representation of the heap, and the root is the first element.

Complete trees must have a height that is bounded by lg N, where N is the number of nodes. Furthermore, the heap property is sufficiently loose that when it is disturbed by replacing the root with another value that violates the heap property, the heap property may be restored in time proportional to the height of the tree—hence the O(N lg N) time bound for performing this restoration N times. If a single node in a heap violates the heap property with respect to its children, we simply swap that node with its larger child, repeating this process as often as needed; it must perforce stop on reaching the leaves. Establishing the heap property in the first place for an arbitrary complete tree is possible in linear time: we simply work backwards from the end of the array, swapping each node with its parent if it is larger than the parent.

In the demonstration below, the portion of the array that is "heapified" is shown in green, and the as-yet unheapified and unsorted elements are in pink. Items that are being compared (parents with child nodes) are marked with "V". Once the array is heapified, each step consists of swapping the root (largest) remaining element of the heap with the last element of the heap (thus removing it from the heap and placing it at the right point in the final array) and then "reheapifying" as needed, swapping the new root downwards until the heap property is restored.