$3.$ For the following Heap Sort algorithm,

a$)$ What are the properties of a Max Heap?

b$)$ For the array A$[$n$]$ represented by a heap, what will the following functions return: PARENT$($i$)$; LEFT$($i$)$; RIGHT$($i$)?$

c$)$ What are the minimum and maximum number of elements in a heap of height h$?$ Why?

d$)$ Is an array that is in sorted decreasing order a min$-$heap? Why?

e$)$ What is the effect of calling MAX$-$HEAPIFY$($A$,$ i$)$ for i $>$ A$.$heap$\_$size$/2?$

g$)$ Write an algorithm to build a heap using MAX$-$HEAPIFY.

h$)$ Illustrate the operation of HEAPSORT on the array A $=[5,13,2,25,7,17,20,8,4].$

MAX$-$HEAPIFY $($A$,$ i$)$

$11=$ LEFT$($i$)$

$2$ r $=$ RIGHT$($i$)$

$3$ if l$$ A$.$heap$-$size and A$[1]>$ A$[$i$]$

$4$ largest $=$ l

$5$ else largest $=$ i

$6$ if r $<$ A$.$heap$-$size and A$[$r$]>$ A$[$largest$]$

$7$ largest $=$ r

$8$ if largest $$ i

$9$ exchange A$[$i$]$ with A$[$largest$]$

$10$ MAX$-$HEAPIFY $($A$,$ largest$)$

$23$