Heapsort

Heapsort is a sorting algorithm that relies on the properties of heap data structures to function correctly. It has a time complexity of $\Theta (\log n)$ and a space complexity of $\Theta (1)$.

If we define an extract max function:

function Extract-Max(A):
	swap(A[1], A[A.size()])
	A.size() -= 1
	Max-Heapify(A, 1)

Then we can define the heapsort algorithm:

function Heapsort(A, n):
	Build-Max-Heap(A, n)
	for each i = n:2 do
		Extract-Max(A)

Since Build-Max-Heap has a time complexity of $O(n)$, and