# W3206 Heap Sort

From Coder Merlin

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

— Merlin, The Coder

## Background[edit]

## 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:

- Build a binary tree using the given array. Starting with the first index as the parent node, continue by using the formula
to determine the left child of each node, and**2(index)+1**to determine the right child of each node. (On further note, use the lower bound of the formula**2(index)+2**to find the parent node of any child).**(index-1)/2** - "Heapify" the tree: The process of reshaping a binary tree into a heap data structure.
- 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.
- Swap the first and last node, and then delete the last node.
- 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.