In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that heap, placing it at the end of the array in a similar manner to Selection sort. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantages of very simple implementation and a more favorable worst-case O(n log n) runtime. Most real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate. Heapsort is an in-place algorithm, but it is not a stable sort. Heapsort was invented by J. W. J. Williams in 1964. The paper also introduced the binary heap as a useful data structure in its own right. In the same year, Robert W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into the treesort algorithm.
Overview The heapsort algorithm can be divided into two phases: heap construction, and heap extraction.
The heap is an implicit data structure which takes no space beyond the array of objects to be sorted; the array is interpreted as a complete binary tree where each array element is a node and each node's parent and child links are defined by simple arithmetic on the array indexes. For a zero-based array, the root node is stored at index 0, and the nodes linked to node i are iLeftChild(i) = 2⋅i + 1 iRightChild(i) = 2⋅i + 2 iParent(i) = floor((i−1) / 2) where the floor function rounds down to the preceding integer. For a more detailed explanation, see Binary heap § Heap implementation. This binary tree is a max-heap when each node is greater than or equal to both of its children. Equivalently, each node is less than or equal to its parent. This rule, applied throughout the tree, results in the maximum node being located at the root of the tree. In the first phase, a heap is built out of the data (see Binary heap § Building a heap). In the second phase, the heap is converted to a sorted array by repeatedly removing the largest element from the heap (the root of the heap), and placing it at the start of the sorted array. The heap is updated after each removal to maintain the heap property. Once all objects have been removed from the heap, the result is a sorted array. Heapsort is normally performed in place. During the first phase, the array is divided into an unsorted prefix and a heap-ordered suffix (initially empty). Each step shrinks the prefix and expands the suffix. When the prefix is empty, this phase is complete. During the second phase, the array is divided into a heap-ordered prefix and a sorted suffix (initially empty). Each step shrinks the prefix and expands the suffix. When the prefix is empty, the array is sorted.
Algorithm The heapsort algorithm begins by rearranging the array into a binary max-heap. The algorithm then repeatedly swaps the root of the heap (the greatest element remaining in the heap) with its last element, which is then declared to be part of the sorted suffix. Then the heap, which was damaged by replacing the root, is repaired so that the greatest element is again at the root. This repeats until only one value remains in the heap. The steps are:
Call the heapify() function on the array. This builds a heap from an array in O(n) operations. Swap the first element of the array (the largest element in the heap) with the final element of the heap. Decrease the considered range of the heap by one. Call the siftDown() function on the array to move the new first element to its correct place in the heap. Go back to step (2) until the remaining array is a single element. The heapify() operation is run once, and is O(n) in performance. The siftDown() function is called n times and requires O(log n) work each time, due to its traversal starting from the root node. Therefore, the performance of this algorithm is O(n + n log n) = O(n log n). The heart of the algorithm is the siftDown() function. This constructs binary heaps out of smaller heaps, and may be thought of in two equivalent ways:
given two binary heaps, and a shared parent node which is not part of either heap, merge them into a single larger binary heap; or given a "damaged" binary heap, where the max-heap property (no child is greater than its parent) holds everywhere except possibly between the root node and its children, repair it to produce an undamaged heap. To establish the max-heap property at the root, up to three nodes must be compared (the root and its two children), and the greatest must be made the root. This is most easily done by finding the greatest child, then comparing that child to the root. There are three cases:
If there are no children (the two original heaps are empty), the heap property trivially holds, and no further action is required. If root is greater than or equal to the greatest child, the heap property holds and likewise, no further action is required. If the root is less than the greatest child, exchange the two nodes. The heap property now holds at the newly promoted node (it is greater than or equal to both of its children, and in fact greater than any descendant), but may be violated between the newly demoted ex-root and its new children. To correct this, repeat the siftDown() operation on the subtree rooted at the newly demoted ex-root. The number of iterations in any one siftdown() call is bounded by the height of the tree, which is ⌊log2 n⌋ = O(log n).
Pseudocode The following is a simple way to implement the algorithm in pseudocode. Arrays are zero-based and swap is used to exchange two elements of the array. Movement 'down' means from the root towards the leaves, or from lower indices to higher. Note that during the sort, the largest element is at the root of the heap at a[0], while at the end of the sort, the largest element is in a[end].
procedure heapsort(a, count) is input: an unordered array a of length count (Build the heap in array a so that largest value is at the root) heapify(a, count)
… excerpt ends here. Continue reading the full article.
