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.

Imagine that we are walking through an array of data, creating nodes for each element, and adding each node to the heap. If we add a node to the last item in the tree, we have no information whatsoever about the last level of the heap, so the node will definitely have to bubble up the node.

Contrast that with the situation of adding a node to the last position of a tree, utilizing a bottom-up construction process. Here, we are adding a root node to an already-sorted subtree. This invokes the down bubble algorithm.

It is a subtle difference, but here's why this works: the maximum distance an element can possibly be moved is proportional to the distance from the insertion point to the point in the heap. If runtime is proportional to the sum of the heights, then for a heap with N nodes, this is O(N).

public static<T> void makeHeap(T[] arr, Comparator<T> comp) { 
    for(int i=arr.length/2; i>=0; i--) { 
        percolateDown(arr, comp, arr.length, i);
    }
}

public static<T> void perclateDown(T[] arr, Comparator<T> comp, int heapSize, int i) { 
    ...
}