Heapsort

Heapsort is using a (binary) Heap-based PriorityQueue for sorting. It has $O(n \lg n)$ performance. This performance is substantially better than all the other (quadratic) sorting algorithms we have studied.

Heapsort is, in a way, similar to selection sort; it repeatedly finds the smallest/largest item and moves it to the front/back of the collection.

The main difference is that instead of scanning through the entire collection to find the smallest/largest item, it uses a heap to find the "best" (max or min) element in sub-linear $O(\lg n)$ time.

In the earlier example, we started with an empty heap (PriorityQueue), then successively inserted each element. This process is an $O(n \lg n)$ operation. It turns out building the heap can be done in linear time! Although the asymptotic efficiency of heapsort remains $O(n \lg n)$.

This alternative method starts by arbitrarily putting the elements in a ranked array representation of a binary heap, thus respecting the shape property and repairing the heap (order) property in linear time.

Aside-1: This latter approach was invented by Robert W Floyd, computer scientist and recipient of Turing Award in 1978.

Aside-2: The original $O(n \lg n)$ approach is called Williams' method after J. W. J. Williams the inventor of binary heaps. Williams invented binary heap for heapsort (not for implementing PriorityQueue).

Resources