IMPLEMENTATION OF A PRIORITY QUEUE
AIM :
To implement priority queue using binary heap.
ALGORITHM :
1. Start the program
2. Define a structure called heapstruct with necessary routines
3. Print “1.insert 2.deletemin 3.display 4.exit”
4. If ‘insert’ insert the given element into the heap
5. If ‘delete min’ delete the root node
6. If ‘display’ display the heap in array order
7. If ‘exit’ stop the program
SOURCE CODE :
#include
#include
#define minpqsize 5
struct heapstruct;
typedef struct heapstruct *ptr;
typedef ptr priorityqueue;
priorityqueue initialize(int);
void insert(int,priorityqueue);
int deletemin(priorityqueue);
int isempty(priorityqueue);
int isfull(priorityqueue);
void print(priorityqueue);
struct heapstruct
{
int capacity;
int size;
int *elements;
};
priorityqueue initialize(int maxelements)
{
priorityqueue h;
if(maxelements
{
printf("priority queue size is too small!\n");
printf("enter greater size :");
scanf("%d",&maxelements);
}
h=(ptr)malloc(sizeof(struct heapstruct));
h->elements=malloc((maxelements+1) *sizeof(int));
h->capacity=maxelements;
h->size=0;
h->elements[0]=-1;
return h;
}
void insert(int x,priorityqueue h)
{
int i;
if(isfull(h))
{
printf("priority queue is full!!\n");
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("priority queue is empty!\n");
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]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;
}
int isempty(priorityqueue h)
{
return h->size==0;
}
int isfull(priorityqueue h)
{
return h->size==h->capacity;
}
void print(priorityqueue h)
{
int i;
for(i=1;i<=h->size;i++)
{
printf("%d\t",h->elements[i]);
}
}
void main()
{
priorityqueue h;
int max,ch,no;
printf("enter the maxelements :");
scanf("%d",max);
h=initialize(max);
do
{
printf("\n1.insert 2.deletemin 3.display 4.exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the number :");
scanf("%d",&no);
insert(no,h);
break;
case 2:
no=deletemin(h);
printf("%d is deleted!\n",no);
break;
case 3:
print(h);
break;
case 4:
printf("bye!!\n");
break;
}}while(ch!=4); }
OUTPUT :
Enter max elements :5
1.insert 2.delete min 3.display 4.exit
1
Enter the number :5
1.insert 2.delete min 3.display 4.exit
1
Enter the number :7
1.insert 2.delete min 3.display 4.exit
1
Enter the number :9
1.insert 2.delete min 3.display 4.exit
1
Enter the number :11
1.insert 2.delete min 3.display 4.exit
1
Enter the number :13
1.insert 2.delete min 3.display 4.exit
3
5 7 9 11 13
1.insert 2.delete min 3.display 4.exit
2
5 is deleted
1.insert 2.delete min 3.display 4.exit
4
Bye!!
Earn upto Rs. 9,000 pm checking Emails. Join now!
No comments:
Post a Comment