W3206 Heap Sort

From Coder Merlin
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder
Heapsort

Background[edit]

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

Algorithm[edit]

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 rebuild a max heap until sorted.

Example[edit]

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[edit]

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.