# Heap Sort

Heaps can be used in sorting an array. In max-heaps, maximum element will always be at the root. Heap Sort uses this property of heap to sort the array.

Consider an array $$ Arr $$ which is to be sorted using Heap Sort.

- Initially build a max heap of elements in $$ Arr $$.
- The root element, that is $$Arr[1]$$, will contain maximum element of $$ Arr $$. After that, swap this element with the last element of $$ Arr $$ and heapify the max heap excluding the last element which is already in its correct position and then decrease the length of heap by one.
- Repeat the step 2, until all the elements are in their correct position.

**Implementation:**

` void heap_sort(int Arr[ ])`

{
int heap_size = N;

build_maxheap(Arr);
for(int i = N; i >= 2 ; i-- )
{
swap|(Arr[ 1 ], Arr[ i ]);
heap_size = heap_size - 1;
max_heapify(Arr, 1, heap_size);
}
}

**Complexity:**

max_heapify has complexity $$ O(logN) $$, build_maxheap has complexity $$O(N)$$ and we run max_heapify $$N-1$$ times in heap_sort function, therefore complexity of heap_sort function is $$O(NlogN)$$.

**Example:**

In the diagram below,initially there is an unsorted array Arr having 6 elements and then max-heap will be built.

After building max-heap, the elements in the array $$Arr$$ will be:

Step 1: 8 is swapped with 5.

Step 2: 8 is disconnected from heap as 8 is in correct position now and.

Step 3: Max-heap is created and 7 is swapped with 3.

Step 4: 7 is disconnected from heap.

Step 5: Max heap is created and 5 is swapped with 1.

Step 6: 5 is disconnected from heap.

Step 7: Max heap is created and 4 is swapped with 3.

Step 8: 4 is disconnected from heap.

Step 9: Max heap is created and 3 is swapped with 1.

Step 10: 3 is disconnected.

After all the steps, we will get a sorted array.