Difference between revisions of "W3206 Heap Sort"

Latest revision as of 09:31, 3 May 2022

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:

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.

@@ Line 1: / Line 1: @@
-[[File:Reflection in a soap bubble edit.jpg|thumb|link=|Reflection in a Soap Bubble]]
+[[File:Heapsort.png|thumb|link=|Heapsort]]
 == Background ==
 * Read [https://en.wikipedia.org/wiki/Heapsort] (Wikipedia)
-* View [https://www.geeksforgeeks.org/heap-sort/] (geeksforgeeks)
+* Read [https://www.geeksforgeeks.org/heap-sort/] (geeksforgeeks)
 * 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).
-# If the element on the left is '''greater than''' the element on the right, swap the elements
+# "Heapify" the tree: The process of reshaping a binary tree into a heap data structure.
-# Repeat steps 1 & 2 until there are no more swaps to complete
+# 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.
-=== Implementation ===
+=== Example ===
-Although the algorithm is simple, the implementation takes a bit more thought. Here are some things to keep in mind:
+Here's an example of a bubble sort for an array with 3 elements:
-* You'll need a variable to count the number of swaps you've made, in total and after each pass
-* Before a swap, you'll need to store one of the values in a '''temporary variable'''
-* You'll need a '''nested loop''' (the outer loop to continue until the array is sorted, and the inner loop to iterate over the array)
-* Consider which type of loop is the best option ('''Hint:''' you'll need the outer loop to always run at least once)
-==== Swaps ====
-You can write the swap implementation within the nested loop or within a separate function. Note that if you choose to write a separate function, you'll want to pass the array into the function '''by reference''' to avoid making a copy of the array each time you need to make a swap. However you choose to implement the swap, you'll need to store at least one of the values (the left or the right) outside of the array. If you just swap without storing one of the values:
 <syntaxhighlight>
-integers[index-1] = integers[index]
+Input data: 4, 10, 3, 5, 1
-integers[index] = integers[index-1]
+(0)
-</syntaxhighlight>
+        /   \
+(1)   3(2)
+    /   \
+(3)    1(4)
-After the execution of the above code, the elements/integers at '''''index''''' and '''''index - 1''''' would be equal to whatever the element/integer at '''''index''''' originally was. In order to solve this, you'll need to store either initial element into a temporary variable, swap the elements, then assign the remaining element to your stored value.
+The numbers in bracket represent the indices in the array
+representation of data.
-=== Example ===
+Applying heapify procedure to index 1:
-Here's an example of a bubble sort for an array with 3 elements:
+(0)
+        /   \
+(1)    3(2)
+    /   \
+(3)    1(4)
-<syntaxhighlight>
+Applying heapify procedure to index 0:
-Array: [42, 82, 40] | Initial, Pass: 0
+(0)
-Array: [42, 40, 82] | Swaps: 1, Pass: 1
+        /  \
-Array: [40, 42, 82] | Swaps: 1, Pass: 2
+(1)  3(2)
-Array: [40, 42, 82] | Swaps: 0, Pass: 3
+    /   \
-Sorted in 3 iterations
+(3)    1(4)
+The heapify procedure calls itself recursively to build heap
+ in top down manner.
 </syntaxhighlight>
-Iteration #
-# The array was initially set to <syntaxhighlight inline>[42, 82, 40]</syntaxhighlight>. Remember that we compare each element with the one before it, so the algorithm will compare '''42''' and '''82''' first. Since 42 < 82, there there's nothing to swap. However, for the next two elements '''82''' and '''40''', 82 > 40 so the elements are swapped.
-# For the second iteration, the array starts at <syntaxhighlight inline>[42, 40, 82]</syntaxhighlight>. The first two elements, '''42''' and '''40''' are compared. Because 42 > 40, the first two elements are swapped. Then, the next two elements: '''42''' and '''82''' are compared. Because 42 < 82, they are already in order and no swaps need to be made.
-# For the third iteration, the array start at <syntaxhighlight inline>Array: [40, 42, 82]</syntaxhighlight>. The first two elements, '''40''' and '''42''' are compared. Because 40 < 42, no swaps need to be made. Then, the next two elements, '''42''' and '''82''' are compared. Because 42 < 82, no swaps need to be made. Because no swaps were made at all in this iteration, we know the array is sorted and we can exit the loop.
 === 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.