EX.NO: 7 IMPLEMENTATION OF PRIORITY QUEUE
AIM:
To write a c program to implement of priority queue.
ALGORITHM:
Step 1: Start the program.
Step 2: INSERT:
* For insertion check that queue is full or not if it is full it shows an error full queue.
* If it is not full then go for the insertion. For insertion create a hole at the last position and bubble the hole up till it satisfies Heap order property
Step 3: DELETE MIN:
* For deleting minimum element , check that priority queue is empty or not if it is empty it shows an error that the priority queue is empty.
* If it is not empty then go for deletion, create a hole at root node and slide the hole down one level till the last element is inserted in an appropriate position.
Step 4: FIND MIN:
* For finding minimum element check that if priority queue is empty or not if it is empty then it shows an error that priority queue is empty, if it is not empty return the root element.
Step 5:Stop the program.
PROGRAM:
#include<stdlib.h>
#include<stdio.h>
#define minpqsize (7)
#define mindata (-32767)
#define error(str) fatalerror(str)
#define fatalerror(str) fprintf(stderr,"%s\n",str),exit(1)
typedef int elementtype;
struct heapstruct;
typedef struct heapstruct *priorityqueue;
priorityqueue initialize(int maxelements);
void destroy(priorityqueue H);
void makeempty(priorityqueue H);
void insert(elementtype x,priorityqueue H);
elementtype deletemin(priorityqueue H);
elementtype findmin(priorityqueue H);
int isempty(priorityqueue H);
int isfull(priorityqueue H);
struct heapstruct
{
int capacity;
int size;
elementtype *elements;
};
priorityqueue initialize(int maxelements)
{
priorityqueue H;
if(maxelements<minpqsize)
error("priorityqueue size is small");
H=malloc(sizeof(struct heapstruct));
if(H==NULL)
fatalerror("out of space!!!");
H->elements=malloc((maxelements+1)*sizeof(elementtype));
if(H->elements==NULL)
fatalerror("out of space!!!");
H->capacity=maxelements;
H->size=0;
H->elements[0]=mindata;
return H;
}
void insert(elementtype x,priorityqueue H)
{
int i;
if(isfull(H))
{
error("priorityqueue 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;
}
elementtype deletemin(priorityqueue H)
{
int i,child;
elementtype minelement,lastelement;
if(isempty(H))
{
error("priorityqueue is empty");
return H->elements[0];
}
minelement=H->elements[1];
lastelement=H->elements[H->size--];
for(i=1;i*2<=H->size;i=child)
{
child=i*2;
if(child!=H->size && H->elements[child+1]<H->elements[child])
child++;
if(lastelement>H->elements[child])
H->elements[i]=H->elements[child];
else
break;
}
H->elements[i]=lastelement;
return minelement;
}
elementtype findmin(priorityqueue H)
{
if(!isempty(H))
return H->elements[1];
error("priorityqueue is empty");
return H->elements[0];
}
void display(priorityqueue H)
{
int i;
for(i=1;i<=H->size;i++)
{
printf("%d",H->elements[i]);
printf("\t");
}
}
int isempty(priorityqueue H)
{
return H->size==0;
}
int isfull(priorityqueue H)
{
return H->size==H->capacity;
}
void main()
{
int size,ch,i;
priorityqueue p;
clrscr();
printf("enter the size of binheap:");
scanf("%d",&size);
p=initialize(size);
do
{
printf("\n*****MENU*****\n1.INSERT\n2.DELETEMIN\n3.FINDMIN\n4.DISPLAY\n5.EXIT\n");
printf(“\n Enter the choice:”);
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the element to be inserted:");
scanf("%d",&i);
insert(i,p);
break;
case 2:
deletemin(p);
break;
case 3:
printf("%d",findmin(p));
break;
case 4:
display(p);
}
}
while(ch!=5);
}
