// Author: Athula Gunawardena     
//  Version 1:  10/18/03 
// 
// heap.h contains a global heap that grows up to 
// MAX_LIMIT; The heap will never be full;
// If it has used the maximum capacity, it accepts 
// the new element to the position of the last leaf

#define MAX_NP_HEAP_LIMIT 100 

shapes heapNP[MAX_NP_HEAP_LIMIT];   // declare a global heap
int heapNP_size=0;


void NPinsert_element(shapes element, int *size, shapes heap[]);
shapes NPremove_element(int *size, shapes heap[]);

void NPswap(shapes *a, shapes *b)
{
 shapes temp;
 temp = *a;
 *a = *b;
 *b = temp;
 }
 
void NPinsert_element(shapes element, int *size, shapes heap[])
{
 int child, parent;
 static int count =0;

 if(*size == MAX_NP_HEAP_LIMIT)
 {
  child =(*size/2)+count;
  if(heap[child].prom_value <= element.prom_value) return;
  // replace the last leaf with the new element
  heap[(*size/2)+count] = element;
  count++;
  if(count = (*size)) count=0;
  }
  else
  {
   heap[*size] = element;
   (*size)++;
   child = (*size)-1;
   }

 if(child !=0) parent = (child-1)/2;

 while( child !=0 && heap[child].prom_value <= heap[parent].prom_value)
 {
  NPswap(&heap[child], &heap[parent]);
 child = parent;
 if(child !=0) parent = (child-1)/2;
 }
 }

shapes NPremove_element(int *size, shapes heap[])
{
 shapes temp;
 int child, parent;

 temp = heap[0];
 heap[0] = heap[*size-1];
 (*size)--;
 if(*size > 1)
 {

 parent=0;
 if(parent*2+2 <= (*size)-1)
 child = (heap[parent*2+1].prom_value < heap[parent*2+2].prom_value)? parent*2+1:parent*2+2;
 if(parent*2 +1 == (*size)-1)
 child = parent*2+1;

 while(parent*2+1 <= (*size)-1 && heap[parent].prom_value > heap[child].prom_value)
 {
  NPswap(&heap[parent], &heap[child]);
  parent =child;
 if(parent*2+2 <= (*size)-1)
 child = (heap[parent*2+1].prom_value < heap[parent*2+2].prom_value)? parent*2+1:parent*2+2;
 if(parent*2+1 == (*size)-1)
 child = parent*2+1;
 }

} // if (*size > 1)
 return temp;
}

void display_NPheap(int size, shapes heap[])
{
 int i;

  printf("Previous Index \n");
 for(i =0; i< size; i++)
  {
  printf(" %d ", heap[i].prev_index);
  if((i+1)% 20 ==0) printf("\n");
  }
  printf("\n");

 printf("Promising  Index\n");
 for(i =0; i< size; i++)
  {
  printf(" %d ", heap[i].prom_value);
  if((i+1)% 20 ==0) printf("\n");
  }
  printf("\n");
  }