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 Big-O 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:

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. 1 point

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

    Does this heap fulfill the properties of a MaxHeap?
  3. 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?
  4. 1 point
    What method do you call after you get rid of the largest node in the heap?
  5. 1 point
    Take this unsorted array [5,32,1,4,2,6,7,9], and sort it in the same format.