How much auxilliary space or overhead (beyond the array holding the records) is needed by Heapsort?
\Theta(1)
\Theta(\log n)
\Theta(n)
\Theta(n^2)
Heapsort does not require any auxilliary arrays.