Heap Sort Idea

Heap Sort Idea video (15 minutes) (Spring 2021)

The Max Heap data structure, with its array representation, gives us an opportunity to implement an in-place sorting algorithm.

This algorithm will accept an array/vector of input.

Without creating any extra storage, the algorithm will sort the array/vector of inputs into ascending order.

We will use a MAX Heap, not a Min Heap, to obtain this final sorted order.

Heap Sort by GeeksforGeeks is is a good 2 minute visualization.

General Algorithm

  1. Given an array of elements as input, build a Max Heap from the elements. This can be done in-place, in the input array, swapping elements to achieve the max heap sorting condition. (The largest element, root of the Max Heap, will be at index 0.)

  2. Swap the first element and the last element. This puts the former root, largest element, at the back of the array.

  3. Decrease the heap size. This "cuts off" the largest element at the back of the array. This starts to separate elements into a sorted section at the back of the array, and an unsorted or "still to be visited" section in the front of the array.

  4. Percolate the new root element down to its proper position in the Max Heap, restoring the Max Heap ordering property

  5. Repeat steps 2 - 4 until the array is sorted, in - place.

Complexity

In phase 1, we insert elements into the Max Heap. Each insertion is O(log(n)), for the height of the heap tree. We perform n insertions. So this phase is O(n(log(n))).

In phase 2, we swap root element and last element, and percolate down values ("swap, top, pop"). Swap and top are O(1). Pop is O(log(n)). We will perform n pops, so this phase is also O(n(log(n)))

O(heapSort) = O(phase1) + O(phase2) = O(n(log(n))) + O(n(log(n))) = O(n(log(n)))

Heap Sort is a comparison based sorting algorithm. We will see other comparison based sorting algorithms that are also O(n(log(n))).

Thanks

Thanks to Brian Foster for writing up these notes based on the video lectures.