Heap Sort

Heaps are data structures with weak sorting - that is, the item at the root node is always guaranteed to be the minimum element, but the only invariant in a heap is that any child node must be smaller than its parent.

Heaps are used in priority queues to keep items in a sorted order. But heaps are also useful for general sorting purposes. The heap sort algorithm starts by constructing a heap (tree data structure) and linking each heap node to a particular element in the original data. Once the heap is constructed, the algorithm removes items one at a time from the root node, and puts them in their final sorted position.

Top-Down Heap Construction

There are several ways to construct a heap. The "normal" or naive way is to walk through the array of elements, adding each node to the last open position in the heap.

(Note that heaps fill in nodes in a left-to-right, top-to-bottom manner.)

If we add an item to the last open position in a tree, and it is smaller than its parent, we simply swap that node with its parent.

This takes O(N log N) time.

However, we can improve the performance of this top-down construction process, by utilizing the fact that we are inserting a node into a sorted tree. This is still O(N log N), but in reality is more like O(N).

Fast, Bottom-Up Heap Construction

We can construct things faster, from O(N log N) to O(N), by utilizing a bottom-up construction process.