/*
*  implementation of a binary heap
*  Nate Weeks, April 2018
*/

#include <stdio.h>
#include <stdlib.h>

// definitions for left child, right child and parent nodes
#define LCHILD(x) (2 * x + 1)
#define RCHILD(x) (2 * x + 2)
#define PARENT(x) ((x - 1) / 2)

typedef struct node{
  int data;
} *node;

typedef struct minHeap {
  int size;
  node *elem;
} *minHeap;

// initialize minHeap with default values
minHeap initMinHeap() {
  minHeap hp = malloc(sizeof(struct minHeap) * 100);
  hp->elem = malloc(sizeof(struct node) * 100);
  hp->size = 0;
  return(hp);
}

// insert node into minHeap with int data
void insertNode(minHeap hp, int data){
  // allocating space
  // if(hp->size){
  //   hp->elem = realloc(hp->elem, (hp->size + 1) * sizeof(node));
  // } else{
  //   hp->elem = malloc(sizeof(node));
  // }

  // initializing the node with value
  node nd;
  nd->data = data;

  // positioning the node at the right position in the min heap
  int i = (hp->size)++ ;  // i++ because we are adding an element - last index
  while(i && nd->data < hp->elem[PARENT(i)]->data) {
    hp->elem[i] = hp->elem[PARENT(i)] ;  // move node up the line until it fits
    i = PARENT(i) ;
  }
  hp->elem[i] = nd;  // set node
}

// function to swap two nodes
void swap(node n1, node n2) {
  node temp = n1;
  n1 = n2 ;
  n2 = temp ;
}

// recursive function to check which of parent, LCHILD and RCHILD are smaller, then swap
void heapify(minHeap hp, int i) {
  // set smallest to equal the smaller number between parent and LCHILD - i = index of parent
  int smallest = (LCHILD(i) < hp->size && hp->elem[LCHILD(i)]->data < hp->elem[i]->data) ? LCHILD(i) : i;
  // set smallest to equal the smaller number between smallest and RCHILD
  if(RCHILD(i) < hp->size && hp->elem[RCHILD(i)]->data < hp->elem[i]->data) {
    smallest = RCHILD(i);
  }
  // if smallest is not the parent, swap and run heapify on the swapped index
  if(smallest != i) {
    swap((hp->elem[i]), (hp->elem[smallest]));
    heapify(hp, smallest);
  }
}

// function to delete first element in minHeap
void deleteNode(minHeap hp) {
  // if the minHeap has a size, delete first element
  if(hp->size) {
    printf("Deleting node %d\n\n", hp->elem[0]->data);
    hp->elem[0] = hp->elem[--(hp->size)]; // set first elem to equal the last elem
    hp->elem = realloc(hp->elem, hp->size * sizeof(node)); // reallocate memory 1 less
    heapify(hp, 0);  // call heapify on the new root element
  } else {
    printf("\nMin Heap is empty!\n");
    free(hp->elem);   // free if empty
  }
}

// function to traverse the minHeap by printing the array
void levelOrderTraversal(minHeap hp) {
  int i;
  printf("min heap: ");
  for(i = 0; i<hp->size; i++) {
    printf("%d ", hp->elem[i]->data);
  }
  printf("\n");
}

int main(){
  //initialize minheap
  minHeap hp = initMinHeap();
  // insert some elements
  insertNode(hp, 1);
  // insertNode(hp, 7);
  // insertNode(hp, 2);
  // insertNode(hp, 3);
  // insertNode(hp, 8);
  // insertNode(hp, 4);
  // insertNode(hp, 6);
  // // print and delete all elements 1 by 1
  // levelOrderTraversal(hp);
  // deleteNode(hp);
  // levelOrderTraversal(hp);
  // deleteNode(hp);
  // levelOrderTraversal(hp);
  // deleteNode(hp);
  // levelOrderTraversal(hp);
  // deleteNode(hp);
  // levelOrderTraversal(hp);
  // deleteNode(hp);
  // levelOrderTraversal(hp);
  // deleteNode(hp);
  // levelOrderTraversal(hp);
  // deleteNode(hp);
  // levelOrderTraversal(hp);
  // deleteNode(hp);

  return 0;
}