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 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).
- "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.