Heap

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e6 + 5;
//Just A Gentle Reminder about MOD
const int mod = 1e9 + 7;


//Heap - Sort

//implementing max  - Heap

void Heapify(int n , vector < int > &arr , int index){


        int smallest_index = index;
        int left_child = smallest_index*2 + 1;
        int right_child = smallest_index*2 + 2;
        if(left_child < n && arr[left_child] > arr[smallest_index]){
            smallest_index = left_child;
        }
        if(right_child < n && arr[right_child] > arr[smallest_index]){
            smallest_index = right_child;
        }

        if(index != smallest_index){
            swap(arr[smallest_index] , arr[index]);
            Heapify(n,arr,smallest_index);
        }

}
//Time Complexity - O(nlogn) for heap sort
//For making max heap or min heap O(n)

//Balanced Binary Tree(Complete Binary Tree)

void BuildHeap(int n , vector < int > &arr){

    int start_index = n/2 - 1;
    for(int i = start_index ; i >= 0 ; i-- ){
            Heapify(n,arr,i);
    }

    /*for(int i = 0 ; i < n; i++ ){
        cout << arr[i] << " ";
    }*/


    //Code Required for Heap - Sort
    int heap_size = n ;
    for(int i = n - 1 ; i > 0 ; i-- ){
        swap(arr[i] , arr[0]);
        heap_size -= 1;
        Heapify(heap_size, arr , 0);
    }

    for(int i = 0 ; i < n; i++ ){
        cout << arr[i] << " ";
    }

}
int main()
{
    fast;
    int n;
    cin >> n ;
    vector < int > arr(n);
    for(int i = 0 ; i < n; i++ ){
        cin >> arr[i];
    }
    BuildHeap(n,arr);























    return 0;
//It's not end it yet
}