Heap sort is one of the O$($n log n$)$ sorts we consider. it relies on the idea of maintaining a list so that the values exhibit the heap property $($usually maximum heap$),$ then removing one value at a time to sort them.

The program should read in the number of values as an integer, allocate the necessary space, then read in all the values provided. Use a helper function, ReadNums$()$ to return the dynamic array, instead of inputting the values in main$().$

Create a function called PrintNums$()$ that prints out the array with a space between each value. Finish with a new line.

Complete a function, HeapSort$().$ You will need to use one or more helper functions to maintain the heap property through the sorting. Use a min$-$heap to sort the numbers in Descending order.

Ex: When the input is:

$6321598$

the output is:

Unsorted:

$321598$

Heapified:

$123598$

$253891$

$359821$

$589321$

$895321$

$985321$

Sorted:

$9853215\mathrm{.}6$ LAB: Heap sort

Heap sort is one of the $)$ sorts we consider. it relies on the idea of maintaining a list so that the

values exhibit the heap property $($usually maximum heap$),$ then removing one value at a time to sort them.

The program should read in the number of values as an integer, allocate the necessary space, then read

in all the values provided. Use a helper function, ReadNums$()$ to return the dynamic array, instead of

inputting the values in main$().$

Create a function called PrintNums$()$ that prints out the array with a space between each value. Finish

with a new line.

Complete a function, HeapSort$().$ You will need to use one or more helper functions to maintain the

heap property through the sorting. Use a min$-$heap to sort the numbers in Descending order.

Ex: When the input is:

$6,3,2,1,5,9,8$

the output is:

Unsorted:

$3,2,1,5,9,8$

Heapified:

$1,2,3,5,9,8$

$2,5,3,8,9,1$

$3,5,9,8,2,1$

$5,8,9,3,2,1$

$8,9,5,3,2,1$

$9,8,5,3,2,1$

Sorted:

$9,8,5,3,2,1$

$526716\mathrm{.}3555276.$qx$3$zqy$7$

#include $=0$