 A run of heapsort sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy theheap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration. | |
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-caseperformance | |
| Best-caseperformance | (distinct keys)[1][2] or (equal keys) |
| Averageperformance | |
| Worst-casespace complexity | total auxiliary |
Incomputer science,heapsort is an efficient,comparison-basedsorting algorithm that reorganizes an input array into aheap (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 toSelection sort.[3]
Although somewhat slower in practice on most machines than a well-implementedquicksort, it has the advantages of very simple implementation and a more favorable worst-caseO(n logn) runtime. Most real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate. Heapsort is anin-place algorithm, but it is not astable sort.
Heapsort was invented byJ. W. J. Williams in 1964.[4] The paper also introduced thebinary heap as a useful data structure in its own right.[5] In the same year,Robert W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into thetreesort algorithm.[5]
The heapsort algorithm can be divided into two phases: heap construction, and heap extraction.
The heap is animplicit data structure which takes no space beyond the array of objects to be sorted; the array is interpreted as acomplete 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 nodei are
iLeftChild(i) = 2⋅i + 1 iRightChild(i) = 2⋅i + 2 iParent(i) = floor((i−1) / 2)
where thefloor function rounds down to the preceding integer. For a more detailed explanation, seeBinary 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 (seeBinary 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 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.
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:
heapify() function on the array. This builds a heap from an array inO(n) operations.siftDown() function on the array to move the new first element to its correct place in the heap.Theheapify() operation is run once, and isO(n) in performance. ThesiftDown() function is calledn times and requiresO(logn) work each time, due to its traversal starting from the root node. Therefore, the performance of this algorithm isO(n +n logn) =O(n logn).
The heart of the algorithm is thesiftDown() function. This constructs binary heaps out of smaller heaps, and may be thought of in two equivalent ways:
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:
siftDown() operation on the subtree rooted at the newly demoted ex-root.The number of iterations in any onesiftdown() call is bounded by the height of the tree, which is⌊log2n⌋ =O(logn).
The following is a simple way to implement the algorithm inpseudocode. Arrays arezero-based andswap 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 ata[0], while at the end of the sort, the largest element is ina[end].
procedure heapsort(a, count)isinput: an unordered arraya of lengthcount(Build the heap in array a so that largest value is at the root) heapify(a, count)(The following loop maintains theinvariants that a[0:end−1] is a heap, andevery element a[end:count−1] beyond end is greater than everything before it,i.e. a[end:count−1] is in sorted order.) end ← countwhile end > 1do(the heap size is reduced by one) end ← end − 1(a[0] is the root and largest value. The swap moves it in front of the sorted elements.) swap(a[end], a[0])(the swap ruined the heap property, so restore it) siftDown(a, 0, end)
The sorting routine uses two subroutines,heapify andsiftDown. The former is the common in-place heap construction routine, while the latter is a common subroutine for implementingheapify.
(Put elements of 'a' in heap order, in-place)procedure heapify(a, count)is(start is initialized to the first leaf node)(the last element in a 0-based array is at index count-1; find the parent of that element) start ← iParent(count-1) + 1while start > 0do(go to the last non-heap node) start ← start − 1(sift down the node at index 'start' to the proper place such that all nodes below the start index are in heap order) siftDown(a, start, count)(after sifting down the root all nodes/elements are in heap order)(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)procedure siftDown(a, root, end)iswhile iLeftChild(root) < enddo(While the root has at least one child) child ← iLeftChild(root)(Left child of root)(If there is a right child and that child is greater)if child+1 < endand a[child] < a[child+1]then child ← child + 1if a[root] < a[child]then swap(a[root], a[child]) root ← child(repeat to continue sifting down the child now)else(The root holds the largest element. Since we may assume the heaps rooted at the children are valid, this means that we are done.)return
Theheapify procedure operates by building small heaps and repeatedly merging them usingsiftDown. It starts with the leaves, observing that they are trivial but valid heaps by themselves, and then adds parents. Starting with elementn/2 and working backwards, each internal node is made the root of a valid heap by sifting down. The last step is sifting down the first element, after which the entire array obeys the heap property.
To see that this takesO(n) time, count the worst-case number ofsiftDown iterations. The last half of the array requires zero iterations, the preceding quarter requires at most one iteration, the eighth before that requires at most two iterations, the sixteenth before that requires at most three, and so on.
Looked at a different way, if we assume everysiftDown call requires the maximum number of iterations, the first half of the array requires one iteration, the first quarter requires one more (total 2), the first eighth requires yet another (total 3), and so on.
This totalsn/2 +n/4 +n/8 + ⋯ = n⋅(1/2 + 1/4 + 1/8 + ⋯), where the infinite sum is a well-knowngeometric series whose sum is1, thus the product is simplyn.
The above is an approximation. The exact worst-case number of comparisons during the heap-construction phase of heapsort is known to be equal to2n − 2s2(n) −e2(n), wheres2(n) is thenumber of 1 bits in the binary representation ofn ande2(n) is thenumber of trailing 0 bits.[6][7]
Although it is convenient to think of the two phases separately, most implementations combine the two, allowing a single instance ofsiftDownto beexpanded inline.[8]: Algorithm H Two variables (here,start andend) keep track of the bounds of the heap area. The portion of the array beforestart is unsorted, while the portion beginning atend is sorted. Heap construction decreasesstart until it is zero, after which heap extraction decreasesend until it is 1 and the array is entirely sorted.
procedure heapsort(a, count)isinput: an unordered arraya of lengthcount start ← floor(count/2) end ← countwhile end > 1doif start > 0then(Heap construction) start ← start − 1else(Heap extraction) end ← end − 1 swap(a[end], a[0])(The following is siftDown(a, start, end)) root ← startwhile iLeftChild(root) < enddo child ← iLeftChild(root)(If there is a right child and that child is greater)if child+1 < endand a[child] < a[child+1]then child ← child + 1if a[root] < a[child]then swap(a[root], a[child]) root ← child(repeat to continue sifting down the child now)elsebreak(return to outer loop)
The description above uses Floyd's improved heap-construction algorithm, which operates inO(n) time and uses the samesiftDown primitive as the heap-extraction phase. Although this algorithm, being both faster and simpler to program, is used by all practical heapsort implementations, Williams' original algorithm may be easier to understand, and is needed to implement a more general binary heappriority queue.
Rather than merging many small heaps, Williams' algorithm maintains one single heap at the front of the array and repeatedly appends an additional element using asiftUp primitive. Being at the end of the array, the new element is a leaf and has no children to worry about, but may violate the heap property by being greater than its parent. In this case, exchange it with its parent and repeat the test until the parent is greater or there is no parent (we have reached the root). In pseudocode, this is:
procedure siftUp(a, end)isinput:a is the array, which heap-ordered up to end-1.end is the node to sift up.while end > 0 parent := iParent(end)if a[parent] < a[end]then(out of max-heap order) swap(a[parent], a[end]) end := parent(continue sifting up)elsereturnprocedure heapify(a, count)is(start with a trivial single-element heap) end := 1while end < count(sift up the node at index end to the proper place such that all nodes above the end index are in heap order) siftUp(a, end) end := end + 1(after sifting up the last node all nodes are in heap order)
To understand why this algorithm can take asymptotically more time to build a heap (O(n logn) vs.O(n) worst case), note that in Floyd's algorithm, almost all the calls tosiftDown operations apply to verysmall heaps. Half the heaps are height-1 trivial heaps and can be skipped entirely, half of the remainder are height-2, and so on. Only two calls are on heaps of sizen/2, and only onesiftDown operation is done on the fulln-element heap. The overall averagesiftDown operation takesO(1) time.
In contrast, in Williams' algorithm most of the calls tosiftUp are made onlarge heaps of heightO(logn). Half of the calls are made with a heap size ofn/2 or more, three-quarters are made with a heap size ofn/4 or more, and so on. Although theaverage number of steps is similar to Floyd's technique,[9]: 3 pre-sorted input will cause the worst case: each added node is sifted up to the root, so the average call tosiftUp will require approximately(log2n − 1)/2 + (log2n − 2)/4 + (log2n − 3)/8 + ⋯= log2n − (1 + 1/2 + 1/4 + ⋯)= log2n − 2 iterations.
Because it is dominated by the second heap-extraction phase, the heapsort algorithm itself hasO(n logn) time complexity using either version of heapify.
Bottom-up heapsort is a variant that reduces the number of comparisons required by a significant factor. While ordinary "top-down" heapsort requires2n log2n +O(n) comparisons worst-case and on average,[10] the bottom-up variant requiresn log2n +O(1) comparisons on average,[10] and1.5n log2n +O(n) in the worst case.[11]
If comparisons are cheap (e.g. integer keys) then the difference is unimportant,[12] as top-down heapsort compares values that have already been loaded from memory. If, however, comparisons require afunction call or other complex logic, then bottom-up heapsort is advantageous.
This is accomplished by using a more elaboratesiftDown procedure. The change improves the linear-time heap-building phase slightly,[13] but is more significant in the second phase. Like top-down heapsort, each iteration of the second phase extracts the top of the heap,a[0], and fills the gap it leaves witha[end], then sifts this latter element down the heap. But this element came from the lowest level of the heap, meaning it is one of the smallest elements in the heap, so the sift-down will likely take many steps to move it back down.[14] In top-down heapsort, each step ofsiftDown requires two comparisons, to find the minimum of three elements: the new node and its two children.
Bottom-up heapsort conceptually replaces the root with a value of −∞ and sifts it down using only one comparison per level (since no child can possibly be less than −∞) until the leaves are reached, then replaces the −∞ with the correct value and sifts itup (again, using one comparison per level) until the correct position is found.
This places the root in the same location as top-downsiftDown, but fewer comparisons are required to find that location. For any singlesiftDown operation, the bottom-up technique is advantageous if the number of downward movements is at least2⁄3 of the height of the tree (when the number of comparisons is4⁄3 times the height for both techniques), and it turns out that this is more than true on average, even for worst-case inputs.[11]
A naïve implementation of this conceptual algorithm would cause some redundant data copying, as the sift-up portion undoes part of the sifting down. A practical implementation searches downward for a leaf where −∞would be placed, then upward for where the rootshould be placed. Finally, the upward traversal continues to the root's starting position, performing no more comparisons but exchanging nodes to complete the necessary rearrangement. This optimized form performs the same number of exchanges as top-downsiftDown.
Because it goes all the way to the bottom and then comes back up, it is calledheapsort with bounce by some authors.[15]
function leafSearch(a, i, end)is j ← iwhile iRightChild(j) < enddo(Determine which of j's two children is the greater)if a[iRightChild(j)] > a[iLeftChild(j)]then j ← iRightChild(j)else j ← iLeftChild(j)(At the last level, there might be only one child)if iLeftChild(j) < endthen j ← iLeftChild(j)return j
The return value of theleafSearch is used in the modifiedsiftDown routine:[11]
procedure siftDown(a, i, end)is j ← leafSearch(a, i, end)while a[i] > a[j]do j ← iParent(j)while j > ido swap(a[i], a[j]) j ← iParent(j)
Bottom-up heapsort was announced as beating quicksort (with median-of-three pivot selection) on arrays of size ≥16000.[10]
A 2008 re-evaluation of this algorithm showed it to be no faster than top-down heapsort for integer keys, presumably because modernbranch prediction nullifies the cost of the predictable comparisons that bottom-up heapsort manages to avoid.[12]
A further refinement does abinary search in the upward search, and sorts in a worst case of(n+1)(log2(n+1) + log2 log2(n+1) + 1.82) +O(log2n) comparisons, approachingthe information-theoretic lower bound ofn log2n − 1.4427n comparisons.[16]
A variant that uses two extra bits per internal node (n−1 bits total for ann-element heap) to cache information about which child is greater (two bits are required to store three cases: left, right, and unknown)[13] uses less thann log2n + 1.1n compares.[17]
Heapsort primarily competes withquicksort, another very efficient general purpose in-place unstable comparison-based sort algorithm.
Heapsort's primary advantages are its simple, non-recursive code, minimal auxiliary storage requirement, and reliably good performance: its best and worst cases are within a small constant factor of each other, and of thetheoretical lower bound on comparison sorts. While it cannot do better thanO(n logn) for pre-sorted inputs, it does not suffer from quicksort'sO(n2) worst case, either.
Real-world quicksort implementations use a variety ofheuristics to avoid the worst case, but that makes their implementation far more complex, and implementations such asintrosort and pattern-defeating quicksort[29] use heapsort as a last-resort fallback if they detect degenerate behaviour. Thus, their worst-case performance is slightly worse than if heapsort had been used from the beginning.
Heapsort's primary disadvantages are its poorlocality of reference and its inherently serial nature; the accesses to the implicit tree are widely scattered and mostly random, and there is no straightforward way to convert it to aparallel algorithm.
The worst-case performance guarantees make heapsort popular inreal-time computing, and systems concerned with maliciously chosen inputs[30] such as the Linux kernel.[31] The combination of small implementation and dependably"good enough" performance make it popular inembedded systems, and generally any application where sorting is not aperformance bottleneck.E.g. heapsort is ideal for sorting a list offilenames for display, but adatabase management system would probably want a more aggressively optimized sorting algorithm.
A well-implemented quicksort is usually 2–3 times faster than heapsort.[19][32] Although quicksort requires fewer comparisons, this is a minor factor. (Results claiming twice as many comparisons are measuring the top-down version; see§ Bottom-up heapsort.) The main advantage of quicksort is its much better locality of reference: partitioning is a linear scan with good spatial locality, and the recursive subdivision has good temporal locality. With additional effort, quicksort can also be implemented in mostlybranch-free code,[33][34] and multiple CPUs can be used to sort subpartitions in parallel. Thus, quicksort is preferred when the additional performance justifies the implementation effort.
The other majorO(n logn) sorting algorithm ismerge sort, but that rarely competes directly with heapsort because it is not in-place. Merge sort's requirement forΩ(n) extra space (roughly half the size of the input) is usually prohibitive except in the situations where merge sort has a clear advantage:
The examples sort the values { 6, 5, 3, 1, 8, 7, 2, 4 } in increasing order using both heap-construction algorithms. The elements being compared are shown in abold font. There are typically two when sifting up, and three when sifting down, although there may be fewer when the top or bottom of the tree is reached.
| Heap | Unsorted | Swap elements |
|---|---|---|
| 6 | 5, 3, 1, 8, 7, 2, 4 | |
| 6,5 | 3, 1, 8, 7, 2, 4 | |
| 6, 5,3 | 1, 8, 7, 2, 4 | |
| 6,5, 3,1 | 8, 7, 2, 4 | |
| 6,5, 3, 1,8 | 7, 2, 4 | 5 ↔ 8 |
| 6,8, 3, 1, 5 | 7, 2, 4 | 6 ↔ 8 |
| 8, 6, 3, 1, 5 | 7, 2, 4 | |
| 8, 6,3, 1, 5,7 | 2, 4 | 3 ↔ 7 |
| 8, 6,7, 1, 5, 3 | 2, 4 | |
| 8, 6,7, 1, 5, 3,2 | 4 | |
| 8, 6, 7,1, 5, 3, 2,4 | 1 ↔ 4 | |
| 8,6, 7,4, 5, 3, 2, 1 |
| Unsorted | Heap | Swap elements |
|---|---|---|
| 6, 5, 3, 1 | 8, 7, 2, 4 | |
| 6, 5, 3 | 1, 8, 7, 2,4 | 1 ↔ 4 |
| 6, 5, 3 | 4, 8, 7, 2,1 | |
| 6, 5 | 3, 4, 8,7,2, 1 | 3 ↔ 7 |
| 6, 5 | 7, 4, 8,3, 2, 1 | |
| 6 | 5, 7,4,8, 3, 2, 1 | 5 ↔ 8 |
| 6 | 8, 7, 4,5, 3, 2, 1 | |
| 6,8,7, 4, 5, 3, 2, 1 | 6 ↔ 8 | |
| 8,6, 7,4,5, 3, 2, 1 |
| Heap | Sorted array | Swap elements | Details |
|---|---|---|---|
| 8, 6, 7, 4, 5, 3, 2,1 | 8 ↔ 1 | Add 8 to the sorted array by swapping it with 1 | |
| 1,6,7, 4, 5, 3, 2 | 8 | 1 ↔ 7 | Swap 1 and 7 as they are not in order in the heap |
| 7, 6,1, 4, 5,3,2 | 8 | 1 ↔ 3 | Swap 1 and 3 as they are not in order in the heap |
| 7, 6, 3, 4, 5,1, 2 | 8 | 1 has no children; siftDown complete | |
| 7, 6, 3, 4, 5, 1,2 | 8 | 7 ↔ 2 | Add 7 to the sorted array by swapping it with 2 |
| 2,6,3, 4, 5, 1 | 7, 8 | 2 ↔ 6 | Swap 2 and 6 as they are not in order in the heap |
| 6,2, 3,4,5, 1 | 7, 8 | 2 ↔ 5 | Swap 2 and 5 as they are not in order in the heap |
| 6, 5, 3, 4,2, 1 | 7, 8 | 2 has no children; siftDown complete | |
| 6, 5, 3, 4, 2,1 | 7, 8 | 6 ↔ 1 | Add 6 to the sorted array by swapping it with 1 |
| 1,5,3, 4, 2 | 6, 7, 8 | 1 ↔ 5 | Swap 1 and 5 as they are not in order in the heap |
| 5,1, 3,4,2 | 6, 7, 8 | 1 ↔ 4 | Swap 1 and 4 as they are not in order in the heap |
| 5, 4, 3,1, 2 | 6, 7, 8 | 1 has no children; siftDown complete | |
| 5, 4, 3, 1,2 | 6, 7, 8 | 5 ↔ 2 | Add 5 to the sorted array by swapping it with 2 |
| 2,4,3, 1 | 5, 6, 7, 8 | 2 ↔ 4 | Swap 2 and 4 as they are not in order in the heap |
| 4,2, 3,1 | 5, 6, 7, 8 | 2 is greater than 1; siftDown complete | |
| 4, 2, 3,1 | 5, 6, 7, 8 | 4 ↔ 1 | Add 4 to the sorted array by swapping it with 1 |
| 1,2,3 | 4, 5, 6, 7, 8 | 1 ↔ 3 | Swap 1 and 3 as they are not in order in the heap |
| 3, 2,1 | 4, 5, 6, 7, 8 | 1 has no children; siftDown complete | |
| 3, 2,1 | 4, 5, 6, 7, 8 | 1 ↔ 3 | Add 3 to the sorted array by swapping it with 1 |
| 1,2 | 3, 4, 5, 6, 7, 8 | 1 ↔ 2 | Swap 1 and 2 as they are not in order in the heap |
| 2,1 | 3, 4, 5, 6, 7, 8 | 1 has no children; siftDown complete | |
| 2,1 | 3, 4, 5, 6, 7, 8 | 2 ↔ 1 | Add 2 to the sorted array by swapping it with 1 |
| 1 | 2, 3, 4, 5, 6, 7, 8 | Add 1 to the sorted array | |
| 1, 2, 3, 4, 5, 6, 7, 8 | Completed |
For lack of a better name we call this enhanced program 'heapsort with bounce.'
Write a sorting routine similar to the heapsort except that it uses a ternary heap.
