#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;

 
//void MinHeapFixup(int a[], int i)
//{
// int j ,temp;
// temp = a[i];
// j = (i-1)/2;
// while(j >= 0 && i != 0)
// {
//  if(a[j] <= temp) break;
//  a[i] = a[j];
//  i = j;
//  j = (i - 1)/2;
// }
// a[i] = temp;
//}

void MinHeapFixup(int a[],int i)
{
 for(int j = (i -1)/2;(j>=0 && i != 0) && a[i] > a[j];i=j,j=(i-1)/2)   swap(a[i],a[j]);
}

void MinHeapAddNumber(int a[], int n, int nNum)
{
 a[n] = nNum;
 MinHeapFixup(a,n);
}

void MinHeapFixdown(int a[],int i,int n)
{
 int j,temp;
 temp = a[i];
 j = 2*i + 1;
 while(j<n)
 {
  if(j+1 < n && a[j + 1] < a[j]) j++;

  if(a[j] >= temp) break;

  a[i] = a[j];
  i = j;
  j = 2*i + 1;
 }
  a[i] = temp;
}

void MinHeapDeleteNumber(int a[],int n)
{
 swap(a[0],a[n-1]);
 MinHeapFixdown(a,0,n - 1);
}

void MakeMinHeap(int a[], int n)
{
 for(int i = n/2 - 1;i>= 0;i--)
     MinHeapFixdown(a,i,n);
}

void Minheapsort(int a[],int n)
{
 for(int i = n-1;i>=1;i--)
 {
   swap(a[i],a[0]);
   MinHeapFixdown(a,0,i);
 }
}
int main()
{
    int a[] = {1,9,5,3,7,2,6,3,4};
    Minheapsort(a,8);
    for(int i = 0;i< 8;i++)
        cout<<a[i]<<" ";
}