Question

The Heapsort algorithm is based on the heap data structure.

The algorithm works by:

1. repeatedly removing the maximum value, i.e. the element at position 0, from the heap;
2. and then restoring the heap property,
3. until the heap is empty.
   

Given the array [73, 57, 0, 47, 8, 9], first turn it into a Max-Heap, and then into a sorted array in ascending order, using the Heapsort algorithm.

You have to show the array content of the heap, as well as a tree representation(**) of the heap, at each step(*).

(*) you may consider one step of the Heapsort algorithm to be one call of the percDown() function as from the Heapsort algorithm implementation presented in textbook section 7.5, figures 7.8.
Alternatively, you may consider one step of the Heapsort algorithm to be one call of the removeMax() function as from the Heapsort heapify() implementation at Lecture 10.

Answer 1

Hope this resolves your doubt.

Please give an upvote if you liked my solution. Thank you :)