# W3206 Heap Sort

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

Heapsort

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