heap sort

// array  is 1 based
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int arr[1000000];
int n;
// heapify function works as .
// compare cur node with both of its child
// if  it is greater than both of  its child than leav
// else swap with the greatest , and call heapify for the node with which we have
// replaced it
void heapify(int n,int cur)// cur is curren node and n is passed so that  it will note access any node out of the  array as a child.
 {
    int lid=2*cur;
    int rid=2*cur+1;
    int maxi=arr[cur];
    int mid=cur;
      if(lid<=n && arr[lid]>maxi)
         {
           maxi=arr[lid];
           mid=lid;
   }
 
   if(rid<=n && arr[rid]>maxi)
         {
           maxi=arr[rid];
           mid=rid;
   }
   if(cur!=mid)
    {
     swap(arr[mid],arr[cur]);
      heapify(n,mid);
}
 
 }

 int heapsort()                                  
  {
   //  a max heap is a heap in which any node contains valeus >= its both child
    // ie  arr[i]>=arr[2*i] and arr[i]>=arr[2*i+1];
    // we are taking  1 based array
    // start building heap from index n/2 since all the nodes from index n/2+1 to n are the leaf nodes
    // also heap is a complete binary tree means nodes will be filled form left to rigsht ..
   
    for(int i=n/2;i>=1;i--)// start building heap from bottom up or from a node at a level 1 above than the leaf.
       {
          heapify(n,i);
}

for(int i=n;i>=1;i--)//  in heach iterqation extract 1 element from the  top of the heap
                     // and decrease size of the array by 1 from end and again build heap to get max of remaining element
                     // at top
 {
      swap(arr[i],arr[1]);
      heapify(i-1,1);
 }
 // printing sorted array ..
 for(int i=n;i>=1;i--)
 {
   cout<<arr[i]<<" ";
 }
  }
 
int main()
{
 cin>>n;
 for(int i=1;i<=n;i++)
  {
    cin>>arr[i];
  }
  heapsort();
}