Heapsort

  • Define heapsort and explain how it relates to (and differs from) selection sort.

Heapsort uses a (binary) heap-based priority queue for sorting. It has $\Omicron(n \lg n)$ performance. This performance is substantially better than all the other (quadratic) sorting algorithms we have studied and is sometimes referred to as quasilinear, log-linear, or linearithmic time.

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 $\Omicron(\lg n)$ time.

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

This alternative method starts by viewing the elements as if they were in a ranked array representation of a binary heap, thus respecting the shape property and then 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 $\Omicron(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