### What is heap sort?

Heap sort is based exclusively upon a binary heap data structure, where we find the largest element and sort it to the end of our unsorted collection. We use the properties of a complete binary tree to sort our collection efficiently.

### Time and Space Complexities:

• Best Time Complexity: O(n log(n))
• Average Time Complexity: O(n log(n))
• Worst Time Complexity: O(n log(n))
• Best Space Complexity: O(1)

• Recursion
• Binary Heap

### Steps to perform heap sort:

1. We start by using Heapify to build a max heap of elements present in an array A.
2. Once the heap is ready, the largest element will be present in the root node of the heap that is A.
3. Now swap the element at A with the last element of the array, and heapify the max heap excluding the last element.
4. Repeat steps 2 and 3 till all the elements in the array are sorted.

### Pseudocode:

```Heapify(A as array, n as int, i as int)
{
max = i
leftchild = 2i + 1
rightchild = 2i + 2

if (leftchild <= n) and (A[i] < A[leftchild])
max = leftchild
else
max = i

if (rightchild <= n) and (A[max]  > A[rightchild])
max = rightchild

if (max != i)
swap(A[i], A[max])
Heapify(A, n, max)
}

Heapsort(A as array)
{
n = length(A)
for i = n/2 downto 1
Heapify(A, n ,i)

for i = n downto 2
exchange A with A[i]
A.heapsize = A.heapsize - 1
Heapify(A, i, 0)
}```