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.

Heap Construction

There are several ways to construct a heap. The "normal" or naive way is to continually add nodes at the root. This bubbles nodes down the tree until they reach the correct final position.

This takes about O(N log N) time.

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.