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:

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

Priority Queue Implementation with all above queue operations

Using C
Using C++


#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