Heapsort is a comparison-based sorting algorithm. Heapsort is part of the selection sort family;
it improves on the basic selection sort by using a logarithmic-time priority queue rather
than a linear-time search. Although somewhat slower in practice on most machines than a
well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n)
runtime. Heapsort is an in-place algorithm, but it is not a stable sort. It was invented
by J. W. J. Williams in 1964.
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((i-1) / 2) 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. 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. Variations
The most important variation to the simple variant is an improvement by R. W. Floyd that,
in practice, gives about a 25% speed improvement by using only one comparison in each siftup
run, which must be followed by a siftdown for the original child. Moreover, it is more
elegant to formulate. Heapsort's natural way of indexing works on indices from 1 up to
the number of items. Therefore the start address of the data should be shifted such that this
logic can be implemented avoiding unnecessary +/- 1 offsets in the coded algorithm. The
worst-case number of comparisons during the Floyd's heap-construction phase of Heapsort
is known to be equal to 2N − 2s2(N) − e2(N), where s2(N) is the sum of all digits of the
binary representation of N and e2(N) is the exponent of 2 in the prime factorization of
N. Ternary heapsort uses a ternary heap instead
of a binary heap; that is, each element in the heap has three children. It is more complicated
to program, but does a constant number of times fewer swap and comparison operations.
This is because each step in the shift operation of a ternary heap requires three comparisons
and one swap, whereas in a binary heap two comparisons and one swap are required. The
ternary heap does two steps in less time than the binary heap requires for three steps,
which multiplies the index by a factor of 9 instead of the factor 8 of three binary
steps. Ternary heapsort is about 12% faster than the simple variant of binary heapsort.
The smoothsort algorithm is a variation of heapsort developed by Edsger Dijkstra in 1981.
Like heapsort, smoothsort's upper bound is O(n log n). The advantage of smoothsort is
that it comes closer to O(n) time if the input is already sorted to some degree, whereas
heapsort averages O(n log n) regardless of the initial sorted state. Due to its complexity,
smoothsort is rarely used. Levcopoulos and Petersson describe a variation
of heapsort based on a Cartesian tree that does not add an element to the heap until
smaller values on both sides of it have already been included in the sorted output. As they
show, this modification can allow the algorithm to sort more quickly than O(n log n) for
inputs that are already nearly sorted. Comparison with other sorts
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 O(n2), 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 O(n log n) 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.
Heapsort also competes with merge sort, which has the same time bounds. Merge sort requires
Ω(n) auxiliary space, but heapsort requires only a constant amount. Heapsort typically
runs faster in practice on machines with small or slow data caches. On the other hand, merge
sort has several advantages over heapsort: Merge sort on arrays has considerably better
data cache performance, often outperforming heapsort on modern desktop computers because
merge sort frequently accesses contiguous memory locations; heapsort references are
spread throughout the heap. Heapsort is not a stable sort; merge sort
is stable. Merge sort parallelizes well and can achieve
close to linear speedup with a trivial implementation; heapsort is not an obvious candidate for a
parallel algorithm. Merge sort can be adapted to operate on singly
linked lists with O(1) extra space. Heapsort can be adapted to operate on doubly linked
lists with only O(1) extra space overhead. Merge sort is used in external sorting; heapsort
is not. Locality of reference is the issue. 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. Pseudocode
The following is the "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].
function heapsort(a, count) is input: an unordered array a of length count
heapify(a, count)
(The following loop maintains the invariants that a[0:end] is a heap and every element
beyond end is greater than everything before it)
end ← count - 1 while end > 0 do
swap(a[end], a[0])
end ← end - 1
siftDown(a, 0, end)
(Put elements of a in heap order, in-place) function heapify(a, count) is
start ← floor / 2)
while start ≥ 0 do (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-1)
start ← start - 1
function siftDown(a, start, end) is root ← start
while root * 2 + 1 ≤ end do child ← root * 2 + 1
swap ← root
if a[swap] < a[child] swap ← child
if child+1 ≤ end and a[swap] < a[child+1] swap ← child + 1
if swap ≠ root swap(a[root], a[swap])
root ← swap else
return
The heapify function can be thought of as building a heap from the bottom up, successively
shifting downward to establish the heap property. An alternative version that builds the heap
top-down and sifts upward may be conceptually simpler to grasp. 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, "broken"
heap and "repairs" it starting from the last non-trivial sub-heap.
Also, the "siftDown" version of heapify has O(n) time complexity, while the "siftUp" version
given below has O(n log n) 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 has an impact on 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 O(n log
n) time complexity using either version of heapify.
function heapify(a,count) is child of the root)
end := 1
while 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, 0, end) end := end + 1
function siftUp(a, start, end) 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 := floor((child - 1) / 2) if a[parent] < a[child] then
swap(a[parent], a[child]) child := parent
else return
Example Let { 6, 5, 3, 1, 8, 7, 2, 4 } be the list
that we want to sort from the smallest to the largest.
1. Build the heap 2. Sorting.
Notes
References Williams, J. W. J., "Algorithm 232 - Heapsort",
Communications of the ACM 7: 347–348 Floyd, Robert W., "Algorithm 245 - Treesort
3", Communications of the ACM 7: 701, doi:10.1145/355588.365103 Carlsson, Svante, "Average-case results on
heapsort", BIT 27: 2–17, doi:10.1007/bf01937350 Knuth, Donald, "§5.2.3, Sorting by Selection",
Sorting and Searching, The Art of Computer Programming 3, Addison-Wesley, pp. 144–155,
ISBN 0-201-89685-0 Thomas H. Cormen, Charles E. Leiserson, Ronald
L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and
McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapters 6 and 7 Respectively: Heapsort and Priority
Queues A PDF of Dijkstra's original paper on Smoothsort
Heaps and Heapsort Tutorial by David Carlson, St. Vincent College
Heaps of Knowledge External links
Animated Sorting Algorithms: Heap Sort – graphical demonstration and discussion of heap sort
Courseware on Heapsort from Univ. Oldenburg - With text, animations and interactive exercises
NIST's Dictionary of Algorithms and Data Structures: Heapsort
Heapsort implemented in 12 languages Sorting revisited by Paul Hsieh
A color graphical Java applet that allows experimentation with initial state and shows
statistics A PowerPoint presentation demonstrating how
Heap sort works that is for educators. Open Data Structures - Section 11.1.3 - Heap-Sort