For HeapSort, give the following:

$-$ What is a heap? How is it used for heap sort?

$-$ Clearly state the Heapsort algorithm.

$-$ Give the efficiency for best, average, and worst cases.

$-$ Give the space complexity.