Heapsort


In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.
Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case big O notation| runtime. Heapsort is an in-place algorithm, but it is not a stable sort.
Heapsort was invented by J. W. J. Williams in 1964. This was also the birth of the heap, presented already by Williams as a useful data structure in its own right. In the same year, R. 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 parts.
In the first step, a heap is built out of the data. The heap is often placed in an array with the layout of a complete binary tree. The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node's parent, left child branch, or right child branch are simple expressions. For a zero-based array, the root node is stored at index 0; if i is the index of the current node, then

 iParent = floor where floor functions map a real number to the smallest leading integer.
 iLeftChild = 2*i + 1
 iRightChild = 2*i + 2

In the second step, a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into 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 can be performed in place. The array can be split into two parts, the sorted array and the heap. The storage of heaps as arrays is diagrammed here. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.

Algorithm

The Heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap. This repeats until the range of considered values is one value in length.
The steps are:
  1. Call the buildMaxHeap function on the list. Also referred to as heapify, this builds a heap from a list in O operations.
  2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
  3. Call the siftDown function on the list to sift the new first element to its appropriate index in the heap.
  4. Go to step unless the considered range of the list is one element.
The buildMaxHeap operation is run once, and is in performance. The siftDown function is, and is called times. Therefore, the performance of this algorithm is.

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, while at the end of the sort, the largest element is in a.
procedure heapsort is
input: an unordered array a of length count

'
heapify
'
end ← count - 1
while end > 0 do
'
swap
'
end ← end - 1
'
siftDown
The sorting routine uses two subroutines, heapify and siftDown. The former is the common in-place heap construction routine, while the latter is a common subroutine for implementing heapify.
'
procedure heapify is
'
'
start ← iParent

while start ≥ 0 do
'
siftDown
'
start ← start - 1
'
'
procedure siftDown is
root ← start
while iLeftChild ≤ end do '
child ← iLeftChild '
swap ← root '
if a < a then
swap ← child
'
if child+1 ≤ end and a < a then
swap ← child + 1
if swap = root then
'
return
else
swap
root ← swap '
The heapify procedure can be thought of as building a heap from the bottom up by successively sifting downward to establish the heap property. An alternative version that builds the heap top-down and sifts upward may be simpler to understand. This siftUp version can be visualized as starting with an empty heap and successively inserting elements, whereas the siftDown version given above treats the entire input array as a full but "broken" heap and "repairs" it starting from the last non-trivial sub-heap.
Also, the siftDown version of heapify has time complexity, while the siftUp version given below has time complexity due to its equivalence with inserting each element, one at a time, into an empty heap.
This may seem counter-intuitive since, at a glance, it is apparent that the former only makes half as many calls to its logarithmic-time sifting function as the latter; i.e., they seem to differ only by a constant factor, which never affects asymptotic analysis.
To grasp the intuition behind this difference in complexity, note that the number of swaps that may occur during any one siftUp call increases with the depth of the node on which the call is made. The crux is that there are many more "deep" nodes than there are "shallow" nodes in a heap, so that siftUp may have its full logarithmic running-time on the approximately linear number of calls made on the nodes at or near the "bottom" of the heap. On the other hand, the number of swaps that may occur during any one siftDown call decreases as the depth of the node on which the call is made increases. Thus, when the siftDown heapify begins and is calling siftDown on the bottom and most numerous node-layers, each sifting call will incur, at most, a number of swaps equal to the "height" of the node on which the sifting call is made. In other words, about half the calls to siftDown will have at most only one swap, then about a quarter of the calls will have at most two swaps, etc.
The heapsort algorithm itself has time complexity using either version of heapify.
procedure heapify is
'
end := 1

while end < count
'
siftUp
end := end + 1
'

procedure siftUp is
input: start represents the limit of how far up the heap to sift.
end is the node to sift up.
child := end
while child > start
parent := iParent
if a < a then '
swap
child := parent '
else
return'''

Variations

Floyd's heap construction

The most important variation to the basic algorithm, which is included in all practical implementations, is a heap-construction algorithm by Floyd which runs in time and uses siftdown rather than siftup, avoiding the need to implement siftup at all.
Rather than starting with a trivial heap and repeatedly adding leaves, Floyd's algorithm starts with the leaves, observing that they are trivial but valid heaps by themselves, and then adds parents. Starting with element 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.
The worst-case number of comparisons during the Floyd's heap-construction phase of Heapsort is known to be equal to, where is the number of 1 bits in the binary representation of and is number of trailing 0 bits.
The standard implementation of Floyd's heap-construction algorithm causes a large number of cache misses once the size of the data exceeds that of the CPU cache. Much better performance on large data sets can be obtained by merging in depth-first order, combining subheaps as soon as possible, rather than combining all subheaps on one level before proceeding to the one above.

Bottom-up heapsort

Bottom-up heapsort is a variant which reduces the number of comparisons required by a significant factor. While ordinary heapsort requires comparisons worst-case and on average, the bottom-up variant requires comparisons on average, and in the worst case.
If comparisons are cheap then the difference is unimportant, as top-down heapsort compares values that have already been loaded from memory. If, however, comparisons require a function call or other complex logic, then bottom-up heapsort is advantageous.
This is accomplished by improving the siftDown procedure. The change improves the linear-time heap-building phase somewhat, but is more significant in the second phase. Like ordinary heapsort, each iteration of the second phase extracts the top of the heap,, and fills the gap it leaves with, then sifts this latter element down the heap. But this element comes 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. In ordinary heapsort, each step of the sift-down requires two comparisons, to find the minimum of three elements: the new node and its two children.
Bottom-up heapsort instead finds the path of largest children to the leaf level of the tree using only one comparison per level. Put another way, it finds a leaf which has the property that it and all of its ancestors are greater than or equal to their siblings. Then, from this leaf, it searches upward for the correct position in that path to insert. This is the same location as ordinary heapsort finds, and requires the same number of exchanges to perform the insert, but fewer comparisons are required to find that location.
Because it goes all the way to the bottom and then comes back up, it is called heapsort with bounce by some authors.
function leafSearch is
j ← i
while iRightChild ≤ end do
'
if a > a then
j ← iRightChild
else
j ← iLeftChild
'
if iLeftChild ≤ end then
j ← iLeftChild
return j
The return value of the leafSearch is used in the modified siftDown routine:
procedure siftDown is
j ← leafSearch
while a > a do
j ← iParent
x ← a
a ← a
while j > i do
swap x, a
j ← iParent
Bottom-up heapsort was announced as beating quicksort on arrays of size ≥16000.
A 2008 re-evaluation of this algorithm showed it to be no faster than ordinary heapsort for integer keys, presumably because modern branch prediction nullifies the cost of the predictable comparisons which bottom-up heapsort manages to avoid.
A further refinement does a binary search in the path to the selected leaf, and sorts in a worst case of comparisons, approaching the information-theoretic lower bound of comparisons.
A variant which uses two extra bits per internal node to cache information about which child is greater uses less than compares.

Other variations

Heapsort primarily competes with quicksort, another very efficient general purpose nearly-in-place comparison-based sort algorithm.
Quicksort is typically somewhat faster due to some factors, but the worst-case running time for quicksort is, which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk. See quicksort for a detailed discussion of this problem and possible solutions.
Thus, because of the upper bound on heapsort's running time and constant upper bound on its auxiliary storage, embedded systems with real-time constraints or systems concerned with security often use heapsort, such as the Linux kernel.
Heapsort also competes with merge sort, which has the same time bounds. Merge sort requires auxiliary space, but heapsort requires only a constant amount. Heapsort typically runs faster in practice on machines with small or slow data caches, and does not require as much external memory. On the other hand, merge sort has several advantages over heapsort:
Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.

Example

Let be the list that we want to sort from the smallest to the largest.
Heapnewly added elementswap elements
null6
65
6, 53
6, 5, 31
6, 5, 3, 18
6, 5, 3, 1, 8 5, 8
6, 8, 3, 1, 56, 8
8, 6, 3, 1, 57
8, 6, 3, 1, 5, 73, 7
8, 6, 7, 1, 5, 32
8, 6, 7, 1, 5, 3, 24
8, 6, 7, 1, 5, 3, 2, 41, 4
8, 6, 7, 4, 5, 3, 2, 1

Heapswap elementsdelete elementsorted arraydetails
8, 6, 7, 4, 5, 3, 2, 18, 1swap 8 and 1 in order to delete 8 from heap
1, 6, 7, 4, 5, 3, 2, 88delete 8 from heap and add to sorted array
1, 6, 7, 4, 5, 3, 21, 78swap 1 and 7 as they are not in order in the heap
7, 6, 1, 4, 5, 3, 21, 38swap 1 and 3 as they are not in order in the heap
7, 6, 3, 4, 5, 1, 27, 28swap 7 and 2 in order to delete 7 from heap
2, 6, 3, 4, 5, 1, 778delete 7 from heap and add to sorted array
2, 6, 3, 4, 5, 12, 67, 8swap 2 and 6 as they are not in order in the heap
6, 2, 3, 4, 5, 12, 57, 8swap 2 and 5 as they are not in order in the heap
6, 5, 3, 4, 2, 16, 17, 8swap 6 and 1 in order to delete 6 from heap
1, 5, 3, 4, 2, 667, 8delete 6 from heap and add to sorted array
1, 5, 3, 4, 21, 56, 7, 8swap 1 and 5 as they are not in order in the heap
5, 1, 3, 4, 21, 46, 7, 8swap 1 and 4 as they are not in order in the heap
5, 4, 3, 1, 25, 26, 7, 8swap 5 and 2 in order to delete 5 from heap
2, 4, 3, 1, 556, 7, 8delete 5 from heap and add to sorted array
2, 4, 3, 12, 45, 6, 7, 8swap 2 and 4 as they are not in order in the heap
4, 2, 3, 14, 15, 6, 7, 8swap 4 and 1 in order to delete 4 from heap
1, 2, 3, 445, 6, 7, 8delete 4 from heap and add to sorted array
1, 2, 31, 34, 5, 6, 7, 8swap 1 and 3 as they are not in order in the heap
3, 2, 13, 14, 5, 6, 7, 8swap 3 and 1 in order to delete 3 from heap
1, 2, 334, 5, 6, 7, 8delete 3 from heap and add to sorted array
1, 21, 23, 4, 5, 6, 7, 8swap 1 and 2 as they are not in order in the heap
2, 12, 13, 4, 5, 6, 7, 8swap 2 and 1 in order to delete 2 from heap
1, 223, 4, 5, 6, 7, 8delete 2 from heap and add to sorted array
112, 3, 4, 5, 6, 7, 8delete 1 from heap and add to sorted array
1, 2, 3, 4, 5, 6, 7, 8completed