# Heap Sort

### 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[1].
3. Now swap the element at A[1] 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[1] with A[i]
A.heapsize = A.heapsize - 1
Heapify(A, i, 0)
}```