W3206 Heap Sort

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Heapsort

Background

• Read [1] (Wikipedia)
• Read [2] (geeksforgeeks)
• View [3] (YouTube)

Algorithm

Heap Sort is a sorting algorithm inspired from a Binary Heap data structure, also known as a Heap Tree. Here is an overview on how it works:

1. Build a binary tree using the given array. Starting with the first index as the parent node, continue by using the formula 2(index)+1 to determine the left child of each node, and 2(index)+2 to determine the right child of each node. (On further note, use the lower bound of the formula (index-1)/2 to find the parent node of any child).
2. "Heapify" the tree: The process of reshaping a binary tree into a heap data structure.
3. Build a max heap from the input data. From bottom up on the node tree, if a child is greater than its root, you would swap the child with the root.
4. Swap the first and last node, and then delete the last node.
5. Recursively "heapify" until sorted.

Example

Here's an example of a bubble sort for an array with 3 elements:

Input data: 4, 10, 3, 5, 1
         4(0)
        /   \
     10(1)   3(2)
    /   \
 5(3)    1(4)

The numbers in bracket represent the indices in the array 
representation of data.

Applying heapify procedure to index 1:
         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)

Applying heapify procedure to index 0:
        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)
The heapify procedure calls itself recursively to build heap
 in top down manner.

Performance

Though comparatively more difficult to implement than other sorting methods and very similar to selection sort, heap sort has the advantage of having a favorable worst-case O(nlogn) runtime. As such, heap sort is regarded as an improved method as opposed to selection sort.