Heapsort
Another important algorithm for sorting is called Heapsort. Heapsort uses the Heap data structure in order to sort the given array of data. Heapsort first builds a Max Heap, where each parent node is greater than the child node. Developed by J. W. J. Williams, Heapsort is a common used sorting algorithm used in place of Quicksort for its more favorable worst case. Its BigO notation for Best Case Performance is Ω(n), O(n log n), and its Worst Case Performance is O(n log n).
To start, you build a Max Heap using the given array. Running MaxHeapify, your heap should fulfill the properties of a Max Heap, where each parent node is greater than the child node. Then, you swap the root of the heap with the size of the array i, the size of the array times, starting at 0. After each swap decrease the heap size by one, excluding the sorted element from the heap. Run MaxHeapify again. Once the for loop finishes running, your array will be sorted from smallest to largest.
Pseudo code:
To start, you build a Max Heap using the given array. Running MaxHeapify, your heap should fulfill the properties of a Max Heap, where each parent node is greater than the child node. Then, you swap the root of the heap with the size of the array i, the size of the array times, starting at 0. After each swap decrease the heap size by one, excluding the sorted element from the heap. Run MaxHeapify again. Once the for loop finishes running, your array will be sorted from smallest to largest.
Pseudo code:
_{Heapsort(A) {
BuildHeap(A)
for i < length(A) downto 2 {
exchange A[1] <> A[i]
heapsize < heapsize 1
Heapify(A, 1)
}
BuildHeap(A) {
heapsize < length(A)
for i < floor( length/2 ) downto 1
Heapify(A, i)
}
Heapify(A, i) {
le < left(i)
ri < right(i)
if (le<=heapsize) and (A[le]>A[i])
largest < le
else
largest < i
if (ri<=heapsize) and (A[ri]>A[largest])
largest < ri
if (largest != i) {
exchange A[i] <> A[largest]
Heapify(A, largest)
}
}
(From }_{http://www.cc.gatech.edu/classes/cs3158_98_fall/heapsort.html)}

1 point
In this heap, which nodes should be swapped in order to fulfill the MaxHeap property?

1 point
Does this heap fulfill the properties of a MaxHeap?

1 point
What node does node 1 have to be swapped with to get rid of itself during the process of the final sorting stage?

1 point
What method do you call after you get rid of the largest node in the heap?

1 point
Take this unsorted array [5,32,1,4,2,6,7,9], and sort it in the same format.

1 point
In this heap, which nodes should be swapped in order to fulfill the MaxHeap property? 
1 point
Does this heap fulfill the properties of a MaxHeap? 
1 point
What node does node 1 have to be swapped with to get rid of itself during the process of the final sorting stage? 
1 pointWhat method do you call after you get rid of the largest node in the heap?

1 pointTake this unsorted array [5,32,1,4,2,6,7,9], and sort it in the same format.