#include <iostream>
using namespace std;

inline int iPARENT(int m)
{
 int result = m + 1;

 result = result >> 1;

 result--;

 return result;
}

inline int iLEFT(int m)
{
 int result = m + 1;

 result = result << 1;

 result--;

 return result;
}

inline int iRIGHT(int m)
{
 int result = m + 1;

 result = (result << 1) + 1;

 result--;

 return result;
}

inline void Swap(int& m, int& n)
{
 int temp;

 temp = m;
 m = n;
 n = temp;
}

void MAXHEAPIFY(int *p, int size, int m);

void BUILDMAXHEAP(int *p, int size);

void HEAPSORT(int *p, int size);

int HEAPMAXIMUM(int *p);

int HEAPEXTRACTMAX(int *p, int& size);

void HEAPINCREASEKEY(int *p, int m, int key);

void MAXHEAPINSERT(int *p, int& size);

int main(int argc, char* argv[])
{
 int A[] = {15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1};

 int iSize = sizeof(A) / sizeof(int);

 BUILDMAXHEAP(&A[0], iSize);
 cout << HEAPEXTRACTMAX(&A[0], iSize) << endl;

 int i;

 for (i=0; i<iSize; i++)
  cout << A[i] << "  ";
 cout << endl;

 cout << iSize << endl;

 return 0;
}

void BUILDMAXHEAP(int *p, int size)
{
 int i;

 for (i=iPARENT(size-1); i>=0; i--)
  MAXHEAPIFY(p, size, i);
}

void HEAPSORT(int *p, int size)
{
 BUILDMAXHEAP(p, size);

 int i, iActualsize;

 iActualsize = size;

 for (i=size-1; i>=1; i--) {
  Swap(p[0], p[i]);
  iActualsize--;
  MAXHEAPIFY(p, iActualsize, 0);
 }

}

int HEAPMAXIMUM(int *p)
{
 return p[0];
}

void MAXHEAPIFY(int *p, int size, int m)
{
 int left, right, iLargest,
  temp = m;
 bool bFlag;

 do {
  if (temp > size / 2)
   break;

  bFlag = false;
  left = iLEFT(temp);
  right = iRIGHT(temp);

  if (left < size && p[left] > p[temp])
   iLargest = left;
  else
   iLargest = temp;

  if (right < size && p[right] > p[iLargest])
   iLargest = right;

  if (iLargest != temp) {
   Swap(p[temp], p[iLargest]);
   temp = iLargest;
   bFlag = true;
  }
 } while (bFlag);

}

int HEAPEXTRACTMAX(int *p, int& size)
{
 if (size < 1) {
  cout << "heap underflow!\n";
  exit(-1);
 }

 int max = p[0];
 p[0] = p[size-1];
 size--;
 MAXHEAPIFY(p, size, 0);

 return max;
}

void HEAPINCREASEKEY(int *p, int m, int key)
{
 if (key < p[m]) {
  cout << "new key is smaller than current key" << endl;
  exit(-1);
 }

 p[m] = key;

 while (m > 0 && p[iPARENT(m)] < p[m]) {
  Swap(p[iPARENT(m)] , p[m]);
  m = iPARENT(m);
 }
}

void MAXHEAPINSERT(int *p, int& size)
{
 size++;
 p[size-1] = -1;
 HEAPINCREASEKEY(p, size-1, 10);
}