Priority Queue Implementation

  

Implementation of Priority Queue

 

struct HeapStruct

{

int Capacity;

int Size;

int *Elements;

};

typedef struct HeapStruct *PriorityQueue;

 

PriorityQueue Initialize(int MaxElements)

{

PriorityQueue H;

if( MaxElements < MIN_PQ_SIZE )

printf(“Error – Priority queue size is too small");

 

H = malloc ( sizeof (struct HeapStruct) );

if( H == NULL )

printf(“Memory Allocation Error.");

 

H->Elements = malloc( (MaxElements+1) * sizeof(int) );

if( H-> Elements == NULL )

printf(“Memory Allocation Error”);

 

H->Capacity = MaxElements;

H->Size = 0;

H->Elements[0] = MIN_DATA;

 

return H;

}

 

 

void Insert( int x, PriorityQueue H)

{

int i;

if( IsFull( H ) )

{

printf(“Error – Priority queue is full");

return;

}

for(i = ++H->size; H->Elements[i/2] > x; i /= 2 )

H->Elements[i] = H->Elements[i/2];

H->Elements[i] = x;

}

 

 

int DeleteMin( PriorityQueue H)

{

int i, Child;

int MinElement, LastElement;

 

if( IsEmpty( H ) )

{

printf(“Error – Priority queue is empty");

return H->Elements[0];

}

 

MinElement = H->Elements[1];

LastElement = H->Elements[H->size--];

 

for( i=1; i*2 <= H->size; i=Child )

{

/* find smaller child */

Child = i*2;

if( ( Child != H->size ) &&

( H->Elements[Child+1] < H->Elements[Child] ) )

Child++;

 

/* percolate one level */

if( LastElement > H->Elements[Child] )

H->Elements[i] = H->Elements[Child];

else

break;

}

H->Elements[i] = LastElement;

return MinElement;

}