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

#define LEFT(i) (2*i + 1)
#define RIGHT(i) (2*i +2)
#define PARENT(i) ((i-1)/2)
#define MAXDEPTH(n) ((int) (log2(n) + 1))
#define DEPTH(i) ((int) (log2(i+1) + 1))
#define FIRSTLEAF(d) ((int) pow(2, d-1))

//define a heapify function pointer
typedef void (*heapifyFunction)(int*, int, int);

//methods for the heap
void printTree(int ar[], int n);
void swap(int ar[], int i, int j);
void minHeapify(int *ar, int n, int i);
void maxHeapify(int *ar, int n, int i);
void minMaxHeapify(int *ar, int n, int i);
void heapSort(int ar[], int n, heapifyFunction heapify);
void buildHeap(int ar[], int n, heapifyFunction heapify);

int main(void) {
 int *h;
 int n;

 //seed the prng
 srand(time(0));

 //get the size
 cout << "How big of a heap do you want?" ;
 cin >> n;

 //create a random heap
 h = new int[n];
 for(int i=0; i<n; i++)
   h[i] = rand() % (2*n);


 printTree(h, n);
 cout << "Build the min heap" << endl;
 buildHeap(h, n, minHeapify);
 printTree(h, n);

 cout << "Build the max heap" << endl;
 buildHeap(h, n, maxHeapify);
 printTree(h, n);

 cout << "Build the min max heap" << endl;
 buildHeap(h, n, minMaxHeapify);
 printTree(h, n);


 cout << "Min Heap Sort" << endl;
 heapSort(h, n, minHeapify);
 for(int i=0; i<n; i++) {
   cout << h[i] << ' ';
 }
 cout << endl;

 cout << "Max Heap Sort" << endl;
 heapSort(h, n, maxHeapify);
 for(int i=0; i<n; i++) {
   cout << h[i] << ' ';
 }
 cout << endl;
 return 0;

}


void
printTree(int ar[], int n) {
 int nil = 1;  //nodes in level
 int eol = 0;  //end of the level
 int i=0;      //index;


 for(i=0; i<n; i++) {
   cout << ar[i] << ' ';
   if(i == eol) {
     //handle end of row
     cout << endl;

     //calculate the end of the next row
     nil = 2 * nil;
     eol = i + nil;
   }
 }

 cout << endl;
}


void
swap(int ar[], int i, int j) {
 int tmp;

 tmp = ar[i];
 ar[i]=ar[j];
 ar[j] = tmp;
}


void
minHeapify(int *ar, int n, int i) {
 int l, r;

 l = LEFT(i);
 r = RIGHT(i);

 //make sure we don' go past the end of the array
 if(l >=n)
   l = i;
 if(r >= n)
   r = i;

 //heap property is already met
 if(ar[i] <= ar[l] && ar[i] <= ar[r])
   return;

 //find out if l is the smallest
 if(ar[l] < ar[r]) {
   //left is the smallest, shift i down
   swap(ar, l, i);
   minHeapify(ar, n, l);
 }  else {
   //right is the smallest shift i down
   swap(ar, r, i);
   minHeapify(ar, n, r);
 }
}


void
maxHeapify(int *ar, int n, int i) {
 int l, r;

 l = LEFT(i);
 r = RIGHT(i);

 //make sure we don' go past the end of the array
 if(l >=n)
   l = i;
 if(r >= n)
   r = i;

 //heap property is already met
 if(ar[i] >= ar[l] && ar[i] >= ar[r])
   return;

 //find out if l is the largest
 if(ar[l] > ar[r]) {
   //left is the largest, shift i down
   swap(ar, l, i);
   maxHeapify(ar, n, l);
 }  else {
   //right is the largest shift i down
   swap(ar, r, i);
   maxHeapify(ar, n, r);
 }
}


void
minMaxHeapify(int *ar, int n, int i) {
 int d = DEPTH(i);
 int l, r;
 l = LEFT(i);
 r = RIGHT(i);

 //make sure we don't go past the end of the array
 if(l >=n)
   l = i;
 if(r >= n)
   r = i;

 if(d % 2) {
   //odd row
   //heap property is already met
   if(ar[i] <= ar[l] && ar[i] <= ar[r])
     return;

   //find out if l is the smallest
   if(ar[l] < ar[r]) {
     //left is the smallest, shift i down
     swap(ar, l, i);
     minMaxHeapify(ar, n, l);
   }  else {
     //right is the smallest shift i down
     swap(ar, r, i);
     minMaxHeapify(ar, n, r);
   }
 } else {
   //even row
   //heap property is already met
   if(ar[i] >= ar[l] && ar[i] >= ar[r])
     return;

   //find out if l is the smallest
   if(ar[l] > ar[r]) {
     //left is the smallest, shift i down
     swap(ar, l, i);
     minMaxHeapify(ar, n, l);
   }  else {
     //right is the smallest shift i down
     swap(ar, r, i);
     minMaxHeapify(ar, n, r);
   }
 }
}



void
buildHeap(int ar[], int n, heapifyFunction heapify) {
 int d = MAXDEPTH(n);
 int fl = FIRSTLEAF(d);

 //start at the bottom of the heap, and build toward the root
 for(int i =  fl; i>=0; i--) {
   (*heapify)(ar, n, i);
 }
}


//sort ar using heaps
void heapSort(int ar[], int n, heapifyFunction heapify) {
 int i;

 //sweep over the array, heap as we go
 for(i=0; i<n-1; i++) {
   buildHeap(ar+i, n-i, heapify);
 }
}