#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include "heap.h"
#define MAX_PQ_SIZE 10000

PRIORITY_QUEUE create_pq( unsigned int max_elements )
{
	PRIORITY_QUEUE H;

	if( max_elements > MAX_PQ_SIZE )
		printf("Priority queue size is too large");


    H = (PRIORITY_QUEUE) malloc ( sizeof (struct heap_struct) );
    if( H == NULL )
        printf("Out of space!!!");

/* Allocate the array + one extra for sentinel */
	H->elements = (struct Node *)malloc((max_elements+1)* sizeof (struct Node));
	if( H->elements == NULL )
		printf("Out of space!!!");

	H->max_heap_size = max_elements;
	H->size = 0;

	return H;
}

/* H->element[0] is a sentinel */
void inQueueMax(Node x, PRIORITY_QUEUE H )
{
	unsigned int i;

	if( H->size == H->max_heap_size)
		printf("Priority queue is full");
	else
	{
		i = ++H->size;                  /*the position of the new element*/
        //while( i/2!=0&&strcmp(H->elements[i/2] , x)<0 )   /*compare with the value of the parent node*/
		while(i/2!=0 &&H->elements[i/2].count<x.count)
		{
           H->elements[i] = H->elements[i/2];  /*swap down*/
           i /= 2;                             /*one level up*/
		}
        H->elements[i] = x;                    /*the finial position*/
	}
}
int showHeap(PRIORITY_QUEUE H )
{
	int i;

	printf("===================================================");

	for (i = 1;i <= H->size;i++)
		printf("%d:%s;\n",H->elements[i].count,H->elements[i].address);

	printf("===================================================\n");
	return H->size;
}
Node deQueueMax (PRIORITY_QUEUE H)
{
    unsigned int i, child;
	Node max_element,last_element;

	if( H->size == 0 )
	{
		printf("Priority queue is empty");
		exit;
	}
	
	max_element = H->elements[1];              //first node is the 
	last_element = H->elements[H->size--];

	for( i=1; i*2 <= H->size; i=child )
	{
		/* find bigger child */
     	child = i*2;
		if( ( child != H->size ) &&  H->elements[child+1].count> H->elements [child].count )
			child++;
		/* percolate one level */
		if( last_element.count< H->elements[child].count )
			H->elements[i] = H->elements[child];
		else
			break;
	}
	H->elements[i] = last_element;

	return max_element;
}
int is_Empty(PRIORITY_QUEUE H)
{
	if(H->size==0)
		return(1);
	else return(0);
}