Priority Queue Tutorial.

What is Priority Queue?

Priority queue is a special type of queue, it store item into queue with associated priority. So that it does not support FIFO( First In First Out) structure.

It supports the following three operations:

  1. InsertWithPriority: Insert an item to the queue with associated priority.
  2. GetNext: remove the element from the queue which has highest priority and return it. It also know as PopElement() or GetMaximum.
  3. PeekAtNext(optional): Get the item with highest priority without removing it.

Priority Queue Implementation with all above queue operations

#include <stdio.h>
#define MAX 5

//Declaration of priority queue
typedef struct
{
	int ele[MAX][MAX];
	int count;
}PQueue;

//Initialize priority queue
void init(PQueue *q)
{
	int i=0;
	q->count = 0;
	 
	//All priority value set to -1
	for( i = 0; i < MAX ; i++ )
	{
		q->ele[i][1] = -1 ; 	
	}
}

//Insert item with priority in queue
void insertWithPriority(PQueue *q, int priority, int item )
{
	int i = 0;
	if( q->count == MAX )
	{
		printf("\nPriority Queue is overflow");
		return;
	}

	for ( i = 0; i < MAX; i++ )
	{
		if( q->ele[i][1] == -1)
			break;
	}
	
	q->ele[i][0] = item;
	q->ele[i][1] = priority;

	q->count++;
	printf("\nInserted item is : %d",item);
}

//Remove & get element with highest priority in queue
int GetNext(PQueue *q, int *item)
{
	int i = 0,max,pos=0;

	if( q->count == 0 )
	{
		printf("\nPriority Queue is underflow");
		return -1;
	}
	
	max = q->ele[0][1];
	for ( i = 1; i < MAX; i++ )
	{
		if( max < q->ele[i][1] )
		{
			pos = i;
			max = q->ele[i][1];
		}
	}
	
	*item = q->ele[pos][0];	
	q->ele[pos][1] = -1;

	q->count--;
	return 0;	
}

//Get element with highest priority without removing it from queue
int PeekAtNext(PQueue *q, int *item)
{
	int i = 0,max,pos=0;

	if( q->count == 0 )
	{
		printf("\nPriority Queue is underflow");
		return -1;
	}
	
	max = q->ele[0][1];
	for ( i = 1; i < MAX; i++ )
	{
		if( max < q->ele[i][1] )
		{
			pos = i;
			max = q->ele[i][1];
		}
	}
	
	*item = q->ele[pos][0];	

	return 0;	
}


int main()
{
	int item;
	PQueue q;
	
	init( &q );

	insertWithPriority( &q, 1, 10 );
	insertWithPriority( &q, 2, 20 );
	insertWithPriority( &q, 3, 30 );
	insertWithPriority( &q, 4, 40 );
	insertWithPriority( &q, 5, 50 );
	insertWithPriority( &q, 6, 60 );

	if( PeekAtNext( &q, &item) == 0 )
		printf("\nPeek Item : %d",item);


	if( GetNext( &q, &item) == 0 )
		printf("\nItem : %d",item);
	
	if( PeekAtNext( &q, &item) == 0 )
		printf("\nPeek Item : %d",item);

	if( GetNext( &q, &item) == 0 )
		printf("\nItem : %d",item);
	if( GetNext( &q, &item) == 0 )
		printf("\nItem : %d",item);

	
	if( PeekAtNext( &q, &item) == 0 )
		printf("\nPeek Item : %d",item);

	if( GetNext( &q, &item) == 0 )
		printf("\nItem : %d",item);
	if( GetNext( &q, &item) == 0 )
		printf("\nItem : %d",item);
	if( GetNext( &q, &item) == 0 )
		printf("\nItem : %d",item);	


	printf("\n");
	
	return 0;
}
    Inserted item is : 10
    Inserted item is : 20
    Inserted item is : 30
    Inserted item is : 40
    Inserted item is : 50
    Priority Queue is overflow
    Peek Item : 50
    Item : 50
    Peek Item : 40
    Item : 40
    Item : 30
    Peek Item : 20
    Item : 20
    Item : 10
    Priority Queue is underflow
#include <iostream>

using namespace std;
#define MAX 5

//Declaration of priority queue
class PQueue
{
	private:
		int ele[MAX][MAX];
		int count;

	public:
		PQueue();
		void insertWithPriority(int priority, int item );
		int GetNext(int *item);
		int PeekAtNext(int *item);
		
};

//Initialize priority queue
PQueue:: PQueue()
{
	int i=0;
	count = 0;
	 
	//All priority value set to -1
	for( i = 0; i < MAX ; i++ )
	{
		ele[i][1] = -1 ; 	
	}
}

//Insert item with priority in queue
void PQueue:: insertWithPriority(int priority, int item )
{
	int i = 0;
	if( count == MAX )
	{
		cout<< "\nPriority Queue is overflow";
		return;
	}

	for ( i = 0; i < MAX; i++ )
	{
		if( ele[i][1] == -1)
			break;
	}
	
	ele[i][0] = item;
	ele[i][1] = priority;

	count++;
	cout<<"\nInserted item is : "<< item;
}

//Remove & get element with highest priority in queue
int PQueue:: GetNext(int *item)
{
	int i = 0,max,pos=0;

	if( count == 0 )
	{
		cout<<"\nPriority Queue is underflow";
		return -1;
	}
	
	max = ele[0][1];
	for ( i = 1; i < MAX; i++ )
	{
		if( max < ele[i][1] )
		{
			pos = i;
			max = ele[i][1];
		}
	}
	
	*item = ele[pos][0];	
	ele[pos][1] = -1;

	count--;
	return 0;	
}

//Get element with highest priority without removing it from queue
int PQueue:: PeekAtNext(int *item)
{
	int i = 0,max,pos=0;

	if( count == 0 )
	{
		cout<<"\nPriority Queue is underflow";
		return -1;
	}
	
	max = ele[0][1];
	for ( i = 1; i < MAX; i++ )
	{
		if( max < ele[i][1] )
		{
			pos = i;
			max = ele[i][1];
		}
	}
	
	*item = ele[pos][0];	

	return 0;	
}


int main()
{
	int item;
	PQueue q = PQueue();
	
	

	q.insertWithPriority( 1, 10 );
	q.insertWithPriority( 2, 20 );
	q.insertWithPriority( 3, 30 );
	q.insertWithPriority( 4, 40 );
	q.insertWithPriority( 5, 50 );
	q.insertWithPriority( 6, 60 );

	if( q.PeekAtNext( &item) == 0 )
		cout<<"\nPeek Item : "<< item;


	if( q.GetNext( &item) == 0 )
		cout<<"\nItem : "<< item;
	
	if( q.PeekAtNext( &item) == 0 )
		cout<<"\nPeek Item : "<< item;

	if( q.GetNext( &item) == 0 )
		cout<<"\nItem : "<< item;
	if( q.GetNext( &item) == 0 )
		cout<<"\nItem : "<< item;

	
	if( q.PeekAtNext( &item) == 0 )
		cout<<"\nPeek Item : "<< item;

	if( q.GetNext( &item) == 0 )
		cout<<"\nItem : "<< item;
	if( q.GetNext( &item) == 0 )
		cout<<"\nItem : "<< item;
	if( q.GetNext( &item) == 0 )
		cout<<"\nItem : "<< item;

	cout<< endl;
	
	return 0;
}

    Inserted item is : 10
    Inserted item is : 20
    Inserted item is : 30
    Inserted item is : 40
    Inserted item is : 50
    Priority Queue is overflow
    Peek Item : 50
    Item : 50
    Peek Item : 40
    Item : 40
    Item : 30
    Peek Item : 20
    Item : 20
    Item : 10
    Priority Queue is underflow








Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.



Comments and Discussions





© https://www.includehelp.com (2015-2018), Some rights reserved.




close Like other websites, this site uses cookies to deliver relevant ads based on your interest, by using our website, you acknowledge that you have read our privacy policy.