A Priority Queue is a data structure that is useful in problems where you need to rapidly find and remove the largest element from a collection of values. An everyday example of a priority queue is the to do list of tasks waiting to be performed.

A more computer-related example of a priority queue is the list of pending processes maintained by an operating system, where the value associated with each element is the priority of the job. For example, it may be necessary to respond rapidly to a key pressed at a terminal before the data is lost when the next key is pressed. On the other hand, the process of copying a listing to a queue of output waiting to be handled by a printer is something that can be postponed for a short period, as long as it is handled eventually. By maintaining processes in a priority queue, those jobs with urgent priority are executed prior to any jobs with less urgent requirements.

This implementation of priority queue has two files. One is the header file that defines a Queue class with all the priority queue related functions such as heapmax(), heapextractmax(), heapincreasekey(), maxheapinsert() and maxheapify(). The other file is the demonstration of how to use this Queue class as a Priority Queue.

The Queue Class

#include<iostream>
using namespace std;
class Queue
{
public:
int heapsize;
int heapmax(int *);
int heapextractmax(int *);
void heapincreasekey(int *,int ,int );
void maxheapinsert(int *,int );
void maxheapify(int *,int );
};
int Queue::heapmax(int *a)
{
if(heapsize<1){
cout<<"underflow"<<endl;
exit(1);
}
return(a[0]);
}
int Queue::heapextractmax(int *a)
{
  if(heapsize<1)
  {
   cout<<"underflow"<<endl;
  exit(1);
  }
int max;
max=a[0];
a[0]=a[heapsize-1];
heapsize=heapsize-1;
maxheapify(a,0);
return max;
}
void Queue::heapincreasekey(int *a,int i,int key)
{
int parent,temp;
if(a[i]>key)
{
cout<<"previous key is greater than this key"<<endl;
return;
}
a[i]=key;
while(i>0)
{
parent=(i-1)/2;
if(a[i]>a[parent])
{
temp=a[i];
a[i]=a[parent];
a[parent]=temp;
}
i=parent;
}
}
void Queue::maxheapinsert(int *a,int key)
{
a[heapsize]=-1;
heapsize=heapsize+1;
heapincreasekey(a,heapsize-1,key);
}
void Queue::maxheapify(int *a,int i)
{
int left,right,largest,temp;
left=2*i+1;
right=2*i+2;
if(left<heapsize && a[i]<a[left])
largest=left;
else
largest=i;
if(right<heapsize && a[right]>a[largest])
largest=right;
if(largest!=i)
{
temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheapify(a,largest);
}
}

Demo using Priority Queue

#include<iostream>
#include"PRIORITY QUEUE.h"
using namespace std;

int main()
{
Queue Queue1;
int size,n;
cout<<" HOW MANY ELEMENTS DO YOU WANT TO ENTER IN AN ARRAY = "<<endl;
cin>>size;
int *a;
a=new int[size];
Queue.heapsize=0;
int choice=1;
while(choice)
{
cout<<" 1-> INSERT AN ELEMENT "<<endl;
cout<<" 2-> PRINT MAXIMUM ELEMENT "<<endl;
cout<<" 3-> EXTRACT MAXIMUM ELEMENT "<<endl;
cin>>choice;
switch(choice)
{
case 1:
cout<<" ENTER ELEMENT IN MAX HEAP"<<endl;
cin>>n;
Queue1.maxheapinsert(a,n);
break;

case 2:
     if(Queue1.heapsize==0)
 {
 cout<<" YOUR ARRAY IS EMPTY "<<endl;
 }
 else
cout<<Queue1.heapmax(a)<<endl;
break;
case 3:
 if(Queue1.heapsize==0)
 {
 cout<<" YOUR ARRAY IS EMPTY "<<endl;
 }
 else
cout<<Queue1.heapextractmax(a)<<endl;
break;
}
}
system("pause");
}
Tagged with: C/C++ languageData structuresSource Code
 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.