RSS

Priority Queue

08 Mar

C++ code for implementing Priority Queue:

 

#include<iostream.h>
#include<conio.h>
int i=0,n=0,l,r,heapsize,smallest,temp,j,B[100],C[100],k;

int parent(int i)
{int x;
if(i%2==0)
x=i%2;
else
x=(i-1)/2;
return x;
}

void minpriority(int A[],int i)
{

l=2*i;//left of i
r=1+l;//right of i
if(l<=heapsize && A[l]<A[i])
smallest=l;
else
smallest=i;
if(r<=heapsize && A[r]<A[smallest])
smallest=r;
if(smallest!=i)
{
temp=A[i];
A[i]=A[smallest];
A[smallest]=temp;
minpriority(A,smallest);
}
}


void buildminpriority(int A[])
{
heapsize=n-1;
for(i=n-1;i>=0;i–)
minpriority(A,i);
}

void decreasekey(int A[],int i,int key)
{
if(key>A[i])
cout<<“New key is greater than current key, hence no decreasing.”<<endl;
else
{A[i]=key;
while(i>=0 && A[parent(i)]>A[i])
{temp=A[i];
A[i]=A[parent(i)];
A[parent(i)]=temp;
i=parent(i);}
}
}


void insert(int A[],int key)
{

A[heapsize]=10000;
decreasekey(A,heapsize,key);
}


void extractmin(int A[],int i)
{int min;
if(heapsize<0)
cout<<“Heap Underflow”<<endl;
else
{min=A[0];
A[0]=A[heapsize];
heapsize=heapsize-1;
minpriority(A,0);
cout<<“Value of Minimum is:”<<min<<endl;
}}









void main()
{

cout<<“Enter the size of the array”<<endl;
cin>>n;

cout<<“Enter the values”<<endl;
for(j=0;j<n;j++)
{cin>>B[j];
}

cout<<“Enter the key”<<endl;
cin>>k;
cout<<“Values of priority queue initially:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;


buildminpriority(B);
cout<<“Values of priority queue after building:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;



extractmin(B,i);
cout<<“Values of priority queue after extracting:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;




decreasekey(C,i,k);
cout<<“Values of priority queue after decreasing key:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;




insert(B,k);
cout<<“Values of priority queue after inserting:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;
}//end main

Advertisements
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: