#include<cstdio>
#include<iostream>
using namespace std;
int Parent(int index)
{
return index>>1; // index/2
}
int LeftChild(int index)
{
return index<<1; // 2 * index
}
int RightChild(int index)
{
return (index<<1) + 1; // (2 * index) + 1
}
void Min_Heapify(int *x, int index, int heapsize)
{
//cout<<"Visit-->"<<index<<endl;
int left = LeftChild(index);
int right = RightChild(index);
int smallest = index;
if(left<=heapsize && x[left]<x[smallest])
{
smallest = left;
}
if(right<=heapsize && x[right]<x[smallest])
{
smallest = right;
}
if(smallest != index)
{
swap(x[smallest], x[index]);
Min_Heapify(x, smallest, heapsize);
}
}
void Build_Min_Heap(int *x, int heapsize)
{
for(int I=(heapsize/2); I>0; I--)
{
Min_Heapify(x, I, heapsize);
}
}
void HeapSort(int *x, int heapsize)
{
Build_Min_Heap(x, heapsize);
for(int I = heapsize; I>1; I-- )
{
swap(x[1], x[I]);
heapsize--;
Min_Heapify(x, 1, heapsize);
}
}
void printArray(int *x, int arraySize)
{
for(int I=0; I<arraySize; I++)
{
cout<<I<<" "<<x[I]<<endl;
}
cout<<endl;
}
int main()
{
//Heap start from index 1
int a[] = {-1,8,3,6,5,4,7,2};
int arraySize = sizeof(a)/sizeof(*a);
printArray(a, arraySize);
//Descending Order
HeapSort(a, arraySize-1);
printArray(a, arraySize);
return 0;
}
