Difference between revisions of "W3206 Heap Sort"
From Coder Merlin
(Created page with "thumb|link=|Reflection in a Soap Bubble == Background == * Read [https://en.wikipedia.org/wiki/Heapsort] (Wikipedia) * View [https://www.geeksforgeeks.org/heap-sort/] (geeksforgeeks) * View [https://www.youtube.com/watch?v=HqPJF2L5h9U] (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: # Build a binary tree us...") |
|||
Line 2: | Line 2: | ||
== Background == | == Background == | ||
* Read [https://en.wikipedia.org/wiki/Heapsort] (Wikipedia) | * Read [https://en.wikipedia.org/wiki/Heapsort] (Wikipedia) | ||
* | * Read [https://www.geeksforgeeks.org/heap-sort/] (geeksforgeeks) | ||
* View [https://www.youtube.com/watch?v=HqPJF2L5h9U] (YouTube) | * View [https://www.youtube.com/watch?v=HqPJF2L5h9U] (YouTube) | ||
Line 9: | Line 9: | ||
# 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). | # 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. | ||
1. 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. | |||
2. Recursively "heapify" until sorted. | |||
=== | === Example === | ||
Here's an example of a bubble sort for an array with 3 elements: | |||
<syntaxhighlight> | <syntaxhighlight> | ||
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. | |||
</syntaxhighlight> | </syntaxhighlight> | ||
=== Performance === | === 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. | 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. |
Revision as of 00:24, 27 April 2022
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.
1. 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. 2. Recursively "heapify" 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.