#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);
  }
}