What is the essence of heap sort?

Answer 1

The essence of heap sort is the heap.

A heap is a complete binary tree. That is; every parent node has two child nodes except the last parent which may have either one or two children depending on the total number of nodes. The last parent in the heap is always the rightmost parent on the lowest level. The minimum size of a heap is 2 elements.

The primary property of a heap is that every parent's value is greater-than or equal-to the values of its child or children. This means that the root node (the top of the heap) always holds the largest value in the heap.

Child nodes are denoted as left and right but the final parent need not have a right child. Where both are present, no order is specified. That is; the left child can either be less-than, equal-to or greater-than the right child. Although it is possible to specify an order (such that left is always less-than or equal to right), there is no benefit in doing so.

Heap sort requires random access and is therefore most efficiently implemented using an array. Sorting can be done in-place in logarithmic time and with minimal space overhead but, like quicksort, it is not stable (equal elements may not be in the same order they were input). While somewhat slower than quick sort, in practice it has a more favourable worst-case of O(n log n).

Heap sort can also be thought of as being an improved selection sort. Like selection sort, the input set is divided into two, with an unsorted set and a sorted set, extracting the largest value from the unsorted set and placing it in the sorted set. However, selection sort requires a linear-time search to locate the largest value, whereas heap-sort can achieve this in constant time (because the largest value is always at the top of the heap). The main overheads are in the initial construction of the heap (which takes linear time) and in repairing the heap after extracting each value (which is logarithmic). Selection sort is reasonably efficient when working with small sets (although an insertion sort is usually more efficient) while heap sort is much better for larger sets but still somewhat slower than quick sort in practice.

An array provides the most compact and efficient storage of a heap because the structure of the heap (the actual links between any child and its parent, in either direction) can be computed using trivial arithmetic. That is; given the zero-based index of any element within the heap, we can determine the indices of the parent and the left and right child as follows:

parent = floor ((index - 1) / 2)

left = 2 * index + 1

right = 2 * index + 2

[The floor function is a standard function which returns the largest integer that is not greater than its argument. That is, floor(0.9) will always return the integer 0 rather than "round up" to 1, because 1 would be greater than 0.9].

Heap sort makes use of two helper functions, one to construct the initial heap and the other to repair the heap each time we extract the largest value (the root value).

The repair algorithm is known as a "sift down" and this requires that we pass the index of the parent to be sifted as well as the index of the last value in the heap. The index of the last value is important because if we pass the index of the last parent in the current heap and that parent has no right child, the "right" equation would produce an index that is greater than the last index, so we must guard against that. Leaf nodes have no children, but the algorithm is such that we never pass the index of a leaf node, so we don't need to guard against the "left" equation producing an invalid index.

The purpose of the sift down algorithm is to examine the parent value with its child value(s) to determine which is the largest. If the parent holds the largest, the algorithm does nothing (the heap is valid for that particular parent). Otherwise, it swaps the parent value with the largest child and if the child is not a leaf, repeats the process for that child. In other words, the original parent value finds its correct place within the heap rooted by that parent.

Construction is an iterative algorithm known as "heapify" that traverses the unordered set in reverse order from the back of the array. On each iteration we locate the parent of the current index, thus we can ignore index 0 since it has no parent (it is the root). Once we have located the parent, we perform a repair (a sift-down) with that parent. Since we work from the back of the array, the heap is effectively built from the bottom up, one layer at a time, with lower values sifting down and thus forcing larger values up. The final iteration places the largest value in the root.

Thus, given an array, a, with n elements, we can implement the heap sort algorithm as follows (in pseudocode):

heapify (a, n)

end = n - 1

while end > 0 do

{

swap (a[0], a[end])

end = end - 1

sift_down (a, 0, end)

}

Given an array a with n elements, the heapify algorithm can be implemented as follows:

start = floor ((n - 2) / 2)

while start >= 0 do

{

sift_down (a, start, n - 1)

start = start - 1

}

Finally, given an array a, with a heap rooted at index start and a last value at index end, the sift_down algorithm can be implemented as follows:

root = start

while root * 2 + 1 <= end do

{

left = root * 2 + 1

swap = root

if a[swap] < a[left] then swap = left

right = left + 1

if right <= end and a[swap] < a[right] then swap = right

if swap == root then return

swap (a[root], a[swap])

root = swap

}