#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

template <class DataType>
void PrintTree(DataType x[], int n);

template <class DataType>
void PrintOneRow(DataType x[], int numRows,
                 int row, int row_begin, int row_end);

int main()
{
  int x[] = {87, 35, 74, 67, 79, 84, 76, 73, 81, 32};

  make_heap(x, x+10);
  PrintTree(x, 10);

  x[10] = 83;
  push_heap(x, x + 11);
  cout << "After push_heap(83):\n\n";
  PrintTree(x, 11);

  pop_heap(x, x+11);
  cout << "After pop_heap( ):\n\n";
  PrintTree(x, 10);

  sort_heap(x, x+10);
  cout << "After sort_heap( ), array contains:\n\n";
  for (int i = 0; i < 10; i++)
    cout << x[i] << "  ";
  cout << endl;
}

/* Print one row of a binary tree.
 *
 *  Receive:  Array x storing the binary tree,
 *            numRows = number of rows,
 *            row = current row being printed
 *            row_begin and row_end, the indices of the
 *              beginning of the row and the end of the row
 *  Output:   One row of the binary tree
 ************************************************************/

template <class DataType>
void PrintOneRow(DataType x[], int numRows,
                 int row, int row_begin, int row_end)
{
  int skip = int(pow(2, numRows - row) - 1);  // space between items on row
  for (int i = row_begin; i <= row_end; i++)
  {
    cout << setw(skip) << " ";
    cout << setw(2) << x[i];
    cout << setw(skip) << " ";
  }
  cout << endl << endl;
}

/* Print a binary tree in tree format
 *
 *  Receive:  Array x storing the binary tree,
 *            n = number of nodes in the tree,
 *  Output:   The binary tree
 ************************************************************/

template <class DataType>
void PrintTree(DataType x[], int n)
{
  int row_begin = 0,  // index of beginning of row
      row_end = 0,    //    "   " end of row
      rowLen,         // length of current row
      numRows = int(ceil(log(n) / log(2)));  // number of rows

  for (int row = 0; row < numRows; row++)
  {
    PrintOneRow(x, numRows, row, row_begin, row_end);
    rowLen = row_end - row_begin + 1;
    row_begin = row_end + 1;
    row_end = min(row_end + 2*(rowLen), n - 1);
  }
}