Heapsort

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

Heapsort is using a (binary) Heap-based PriorityQueue for sorting. It has O(nlg⁡n)\Omicron(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)\Omicron(\lg n) time.

In the earlier example, we started with an empty heap (PriorityQueue), then successively inserted each element. This process is an O(nlg⁡n)\Omicron(n \lg n) operation. It turns out building the heap can be done in linear time! Although the asymptotic efficiency of heapsort remains O(nlg⁡n)\Omicron(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(nlg⁡n)\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