/*  Heaps and Heap Sort  - sample solution */

using namespace std;
#include<iostream>
#include<stdlib.h>
#include<time.h>

class heap
{
private:
  int HEAPMAX;
  int *H;
  int last; // last valid index;  
public:   
  heap(int hs) 
  { last = 0; 
    HEAPMAX = hs;
    H = new int[HEAPMAX];
  }
  ~heap() { delete(H); }  

  int parent(int i) { return i/2; }
  int lchild(int i) { return (i*2); }
  int rchild(int i) { return (i*2)+1; }

  void insert(int x) // insert x into heap
  {
    int temp;
    H[++last] = x; // first put x at end of heap;
    int i = last;
    // propagate upwards  
    while (i>1 && (H[i]>H[parent(i)]))
      {
	temp = H[i];
	H[i] = H[parent(i)];
	H[parent(i)] = temp;
	i = parent(i);
      }
  } // insert

  int deleteMax()  // delete the root element
  { 
    // put last value at root, then propagate downwards
    int temp, root;   // for swap
    root = H[1];
    H[1] = H[last];
    H[last--] = root;
    int i = 1;
    while (i<last && ((lchild(i)<=last && H[i]<H[lchild(i)])
		      || (rchild(i)<=last && H[i]<H[rchild(i)])))
      {
	// find the larger of the two childeren, and swap:
        int s;
	if ((rchild(i)>last) || (H[lchild(i)] > H[rchild(i)])) s = lchild(i);
   	   else s = rchild(i);
	// swap 
	temp = H[i];
	H[i] = H[s];
	H[s] = temp;
	i = s;  
      }
    return root;
  } // deleteMax

  /*
   Now to sort an array
  */
  void heapsort(int *A, int sizeofA)
  {
    // insert A elements into H:
    last = 0;
    for(int i=0;i<sizeofA;i++) insert(A[i]);
    // delete elements form Heap:
    for(int i=sizeofA-1;i>=0;i--) A[i]=deleteMax();
  }

};  // heap


int main(int argc, char** argv)
{
  int n;  // size of array, determined by command-line argument
  int *A; // array to be dynamically created
  clock_t t1, t2;  // for time measurements
  n = atoi(argv[1]);   // first command-line argument
  A = new int[n];
  for(int i=0;i<n;i++) A[i] = random(); 
  heap *Hp = new heap(n);
  t1 = clock();
  Hp->heapsort(A,n);
  t2 = clock();

  //  for(int i=0;i<n;i++) cout << A[i] << " ";
  delete(A);
  cout << "\ntime ~= " << (t2-t1)/((double)CLOCKS_PER_SEC) << " seconds\n";
  return 0;
}