/* 
* Code example for CP264 Data Structures II
* simple max-heap
* HBF 
*/

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

int size = 0;
void display_array(int *, int);
int find_max(int *); 
void insert(int*, int);
void delete_max(int *);
void heapify_up(int *, int);
void heapify_down(int *, int, int);
void heapify_up2(int *, int);
void heapify_down2(int *, int, int);
void heap_sort(int a[], int n);  //sort array in increasing order by heap sort, in place
void heap_sort2(int a[], int n);

int main(int argc, char *args[]) {
  int Heap[MAX];
  int n = 20;
  if (argc >1) n = atoi(args[1]);
  
  printf("\nInsert into heap:");
  int i;
  for (i = 0; i < n; i++) {
    insert(Heap, i);
  }
  
  printf("Display heap:\n");
  display_array(Heap, n);

  printf("\nSequece of find_max and delete_max:\n");
  for (i = 0; i < n; i++) {
    printf("%d ", find_max(Heap));
    delete_max(Heap);
  }
  
  printf("\nHeap sort testing\n");
  //in place heap sort, 
  int a[n]; 
  for (i = 0; i < n; i++) {
    a[i] = rand()%n;
  }
  printf("Before heap sort:\n");
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }  
  printf("\n");
 
  heap_sort2(a, n);
  printf("After heap sort:\n");
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  return 0;
}

void display_array(int *Heap, int n) {
  int i;
  for (i=0; i < n; i++)
    printf("%d ", Heap[i]);
}

int find_max(int *Heap) {
  return Heap[0];
}

void insert(int *Heap, int value) {
  Heap[size] = value;   
  heapify_up(Heap, size);
  size++;  
}

void delete_max(int *Heap) {
  size--;	
  Heap[0] = Heap[size];
  heapify_down2(Heap, 0, size);
}

/*  
 * @param Heap - start pointer of binary heap array 
 * @param index - start position of heapify up
*/
void heapify_up(int *Heap, int index) {
  int parent, temp, val = Heap[index]; 
  while (index >0) {  
    parent = (index-1) >> 1;  //equivalent to parent = (index-1)/ 2;
    if (parent < 0 || Heap[parent] >= val)  // stop of parent key is bigger than current node key
		break;
    else { // swap
      temp = Heap[index];		
      Heap[index] = Heap[parent];
      Heap[parent] = temp;
	  index = parent;   // update index for next iteration
    }
  }
}

/*  
 * @param Heap - start pointer of binary heap array 
 * @param index - start position of heapify down
 * @param n - the size of heap
*/
void heapify_down(int *Heap, int index, int n) {
  int child;
  int temp;
  int val = Heap[index]; 
  while (index >=0 && index < n) { // if the current node index is within the range 
    child = (index << 1) + 1;  //get left child index, equivalent to child = index * 2 + 1; 
	if ((child < n-1) && (Heap[child] < Heap[child+1])) child++;    // get the index of a bigger key node index
    if (child >=n || Heap[child] < val) 
		break;   // stop if both children have key values less the val, or child index is out of range.   
    else {
	  temp = Heap[child];	// swap values at index and child
      Heap[child] = Heap[index];  //change key value by the bigger child's value 
      Heap[index] = temp;  
	  index = child;    // update index for next iteration
    }
  }
}


/*  Improved version without swap in iteration
 * @param Heap - start pointer of binary heap array 
 * @param index - start position of heapify
*/
void heapify_up2(int *Heap, int index) {
  int parent, val = Heap[index]; 
  while (index) {
    parent = (index-1) >> 1;  //equivalent to parent = (index-1)/ 2;
    if (Heap[parent] >= val) break;
    else {	
      Heap[index] = Heap[parent];
      index = parent;
    }
  }
  Heap[index] = val;
}

/* Improved version without swap in iteration
 * @param Heap - start pointer of binary heap array 
 * @param index - start position of heapify
 * @param n - the size of heap
*/
void heapify_down2(int *Heap, int index, int n) {
  int val = Heap[index];
  int child = (index << 1) + 1;  //left child, equivalent to child = index * 2 + 1;
  while (index >= 0 && index <n) {  
    child = (index << 1) + 1;  //left child, equivalent to child = index * 2 + 1;
    if ((child+1 < n) && (Heap[child] < Heap[child+1])) child++; 
    if (Heap[child] < val)
      break;   // the both children has key values less the val, done stop.   
    else {
      Heap[index] = Heap[child];  //change key value by the bigger child's value 
      index = child; 
    }
  }
  Heap[index] = val; 
}


/*
*  heap sort given array, increasing order, using max-heap, time: O(n log n), space: O(1), in place
*/
void heap_sort(int a[], int n) {
  int i, index, swindex, val;
  for (i=0; i<n; i++) {  // convert a[n] to max-heap by inserting a[i] for i=0 .. n-1  
    index = i;           //heapify-up from index = i
    val = a[index];
    while (index > 0) {
      swindex = (index-1) >> 1;  //equivalent to swindex = (index-1)/ 2;
      if (a[swindex] >= val) break;
      else {
        a[index] = a[swindex];
        index = swindex;
      }
    }
    a[index] = val;      // end of heapify-up	
  } 
  
  for (i=n-1; i>=0; i--) { // extract max and put at a[i] for i=n-1, ... 0.
     val = a[i];   // get value at a[i] 
     a[i] = a[0];  // put max element to position a[i]
     a[0] = val;  	 
	 index = 0;    //heapify-down from index = 0 on current max-heap a[0..i-1] 
     while (index <= i-1) {     // if has the left child 
       swindex = (index << 1) + 1;  //left child, equivalent to swindex = index * 2 + 1;   
	   if ((swindex+1 < i-1) && (a[swindex] < a[swindex+1])) 
          swindex++;  // swindex is now the child of bigger key
       if (swindex >= i-1 || a[swindex] < val)
          break;      // the both children has key values less the val, done stop.   
       else {
         a[index] = a[swindex]; //change key value by the bigger child's value 
         index = swindex; 
       }
     }
     a[index] = val;  // end of heapify-down
  }
}


void heap_sort2(int a[], int n) {
  int i, index, swindex, val;
  for (i = 0; i<n; i++) {  // convert a[n] to max-heap by inserting a[i] for i=0 .. n-1  
	heapify_up(a, i);
  } 
  for (i=n-1; i>=0; i--) { // extract max and put at a[i] for i=n-1, ... 0.
     val = a[i];   // get value at a[i] 
     a[i] = a[0];  // put max element to position a[i]
     a[0] = val;  	 
	 heapify_down(a, 0, i-1);
  }
}