EX.
NO: IMPLEMENTATION OF PRIORITY QUEUE
DATE:
AIM:
To implement a priority queue using an array.
ALGORITHM:
STEP 1: Define a structure called heap,with data members-
capacity,size,elements.
STEP 2: Declare a pointer pq to the structure heap.
Declare h of type pq.
STEP 3: initialize function:
i. Allocate memory for h.
ii.Allocate memory for array elements.
iii.Iniatialize capacity to max,size to zero,and 1'st element in the heap
to -100.
iv. Return h.
STEP 4: isempty function:
i. Return 1 if the size of the heap is zero.
STEP 5: isfull function:
i. Return 1 if the size and capacity of the heap are equal.
STEP 6: insert function:
i. Initialize i.
ii. If the heap is full print "HEAP IS FULL".
iii. Use a for loop with initial condition i=++h->size check the
condition if the parent of the element in the heap is greater the
element inserted
a. Initialize h->element[i] with its parent.
b. Initialize i=i/2 and continue the for loop.
iv. Initialize h->element[i] to x.
STEP 7: deletemin function:
i. Initialize i and child.
ii. Initialize minelement and lastelement .
iii.Initialize minelement to 1st element in the heap and lastelement
to h->element[h->size--].
iv.Use a for loop with the initialize condition i=2,check if i*2 is less
than or equal to the size of the heap
a. Initialize child to 2*i.
b. Check if child != h->size and element in child+1 is lesser
than element in child position.
c. Increment child .
v.Check another condition,if lastelement is greater than h
->element[child]
2a. if yes then initialize h->element[i] to h->element[child].
2b. else break
vi. Initialize i=child and continue the for loop.
vii. Initialize h->element[i] to lastelement.
viii. Return minelement.
STEP 8: find function:
i.Initialize i.
ii.Use a for loop with the initial condition i=1,check if i is less than or
equal to size of the heap.
a. If h->element[i] is equal to x, print "ELEMENT FOUND IN i
POSITION .
b. Increment i.
iii. Print "ELEMENT NOT FOUND".
STEP 9: display function:
Use a for loop with initial condition i=1, check if i is les than or equal
to the size of the heap.
a) Print h->element[i].
STEP 10: Main ( )
a)Initialise ch,n,x.
b)Get the number of elements
c)Initialise the queue h nd call initial ( )function
d)Get the choice from the user displaying the menu
1.Insert 2.Deletemin 3.Find 4.Display
i)for case 1 get the element to be inserted and call insert ( ) and
then display ( )
ii) for case 2 display minimum value and call deletemin ( )
iii)for case 3 get the element to be searched and call the find ( )
iv) for case 4 call the display ( ) function.
STEP 11: Stop.
CODE:
#include<stdio.h>
struct heap;
typedef struct heap *pq;
struct heap
{
int capacity;
int size;
int *elements;
};
pq h;
pq initial(int max)
{
/*if(max<minheap)
printf("\n heap size is too small");*/
h=malloc(sizeof(struct heap));
if(h==NULL)
printf("\n out of space");
h->elements=malloc((max+1)*sizeof(int));
if(h->elements==NULL)
printf("\n out of space\n");
h->capacity=max;
h->size=0;
h->elements[0]=-100;
return h;
}
int isfull(pq h)
{
return h->size==h->capacity;
}
int isempty(pq h)
{
return h->size==0;
}
void insert(int x,pq h)
{
int i;
if(isfull(h))
{
printf("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(pq h)
{
int i,child;
int minelement,lastelement;
if(isempty(h))
{
printf("\n priority queue is full");
return h->elements[0];
}
minelement=h->elements[1];
lastelement=h->elements[h->size--];
for(i=1;i*2<=h->size;i=child)
{
child=2*i;
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;
}
void find(int x,pq h)
{
int i;
for(i=1;i<=h->size;i++)
{
if(h->elements[i]==x)
{
printf("\nelement found in position %d",i);
return;
}
}
printf("\nelement not found in the heap");
}
void display(pq h)
{
int i;
printf("\n THE PRIORITY QUEUE IS:");
for(i=1;i<=h->size;i++)
printf("\n %d",h->elements[i]);
}
main()
{
int ch,n,x;
pq h;
printf("\n enter the no of elements:");
scanf("%d",&n);
h=initial(n);
while(1)
{
printf("\n enter your choice:");
printf("\n1.insert\n2.deletemin\n3.find\n4.display\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n enter the number to be inserted");
scanf("%d",&x);
insert(x,h);
display(h);
break;
case 2:
printf("\n the minimum element is:");
deletemin(h);
display(h);
break;
case 3:
printf("\n enter the element to be searched:");
scanf("%d",&x);
find(x,h);
break;
case 4:
display(h);
break;
default:
exit(0);
}
}
}
OUTPUT:
Enter the number of elements :5
1.Insert
2.Deletemin
3.Find
4.Exit Enter ur choice:1
Enter the number to be inserted:3
PRIORITY QUEUE IS
3
1.Insert
2.Deletemin
3.Find
4.Exit Enter ur choice:1
Enter the number to be inserted:5
PRIORITY QUEUE IS
3
5
1.Insert
2.Deletemin
3.Find
4.Exit Enter ur choice:1
Enter the number to be inserted:1
PRIORITY QUEUE IS
1
3
5
1.Insert
2.Deletemin
3.Find
4.Exit Enter ur choice:3
Enter the element to be searched 3
Element found in position 2
1.Insert
2.Deletemin
3.Find
4.Exit Enter ur choice:2
PRIORITY QUEUE IS
3
5
1.Insert
2.Deletemin
3.Find
4.Exit Enter ur choice:
1.Insert
2.Deletemin
3.Find
4.Exit Enter ur choice:2
RESULT:
Thus the program to implement priority queue is done successfully and
executed.
