# Heap Sort

Steps:
If we want to sort in ascending then we create a min heap
If we want to create in descending then we create in max heap

Once the heap is created we delete the root node from heap and put the last node in the root position and repeat the steps till we have covered all the elements.
For ascending order:
1. Build Heap
2. Transform the heap into min heap
3. Delete the root node

pseudocode:

```Heapsort(A as array)
BuildHeap(A)
for i = n to 1
swap(A[1], A[i])
n = n - 1
Heapify(A, 1)

BuildHeap(A as array)
n = elements_in(A)
for i = floor(n/2) to 1
Heapify(A,i,n)

Heapify(A as array, i as int, n as int)
left = 2i
right = 2i+1

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

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

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

Implemented code:

```//this is descending order max-heapify

#include<bits/stdc++.h>
using namespace std;
//swapping numbers using call by reference
int swaps(int *p,int *q)
{
int temp=*q;
*q=*p;
*p=temp;
}

//this max heapify ensure that child node is always smaller than the parent node
MaxHeapify(int ary[],int n,int i){
int largest=i;
int    left=2*i+1;
int     right=2*i+2;
if(left<n && ary[left]>ary[largest])
{
largest=left;
}
if(right<n && ary[right]>ary[largest])
{
largest=right;
}
if(largest!=i)
{
swaps(&ary[i],&ary[largest]);
MaxHeapify(ary,n,largest);
}
}

//building heap
void BuildHeap(int ary[],int n)
{
int i;
for(i=floor(n/2)-1;i>=0;i--){
MaxHeapify(ary,n,i);
}
}

//heapSort function sorting the array
void heapSort(int ary[],int n)
{
BuildHeap(ary,n);
for(int i=n-1;i>0;i--){
swaps(&ary[0],&ary[i]);
int heap_size=i;
MaxHeapify(ary,heap_size,0);
}
}
//utility function
void printAry(int ary[],int n)
{
for(int i=0;i<n;i++)
{
cout<<ary[i]<<" ";
}
}
//driver program
int main(){
int ary[]={40,60,10,20,50,30};
int n=sizeof(ary)/sizeof(ary[0]);
heapSort(ary,n);
cout<<"Sorted array:";
printAry(ary,n);

}
```

output:

```Sorted array:10 20 30 40 50 60
```

Complexity Analysis:
Time Complexity for MaxHeapify: O(logn)
Complexity for BuildHeap: O(n)
Complexity of heapSort:
Worst, Avergae, Base case: O(n*logn)
It is inplace algorithm.
Space Complexity: O(1)

It would be a great help, if you support by sharing :)
Author: zakilive