What is Priority Queue?

Share

Priority Queue is a special type of queue in which each element of queue is associated with a priority value. And these elements are served on the basis of their priority value. that is, higher priority elements are served first for queue operation. And if elements have the same priority value then they are served according to their order in the queue.

Difference between Priority Queue and Normal Queue

In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are removed on the basis of priority. The element with the highest priority is removed first.

Fig. Priority Queue

Types of Priority queue

  1. Ascending Priority queue (Min priority Queue)
  2. Descending Priority queue(Max priority Queue)
  1. Ascending Priority Queue is collection of items into which items can be inserted arbitrarily and from which only the smallest items can be removed first. It gives the highest priority to the lower number in that queue. It is also called Min priority queue.
fig . Ascending priority queue

2. Descending priority queue is collection of items into which items can be inserted arbitrarily and from which only the largest items can be removed first. It gives the highest priority to the larger number in that queue. It is also called the Max priority queue.

fig . descending priority queue

Priority Queue Array Implementation

It can be implemented in two ways :

  • Using ordered Array : In ordered array insertion or enqueue operation takes O(n) time complexity because it enters elements in sorted order in queue. And deletion takes O(1) time complexity. 
  • Using unordered Array :In unordered array deletion takes O(n) time complexity because it search for the element in Queue for the deletion and enqueue takes o(1) time complexity.

Steps for Implementing Priority Queue in C

Insertion

  1. Ask the data and its priority from the user.
  2. If front is equal to 0 and rear is equal to n-1 then Queue is full.
  3. Else if front is equal to the -1 them queue is empty so we have initialize front and rear with 0.
  4. Insert the data entered by user in Queue using rear.
  5. If rear is equal to n-1 and front is not equal to 0 then there is empty space in queue before the front for using that space we will shift the elements of the queue with the help of front and rear.
  6. Insert the data in the queue before at the position where given priority is greater then priority of the element in queue.

Deletion

  1. Remove the element and the priority from the front of the queue.
  2. Increase front with 1.

 Print

  1. Using loop take the starting point from the front of the queue and ending point from the rear of the queue and print the data.

Algorithm to implement Priority Queue using Array

  • Enqueue()
    1. IF((Front == 0)&&(Rear == N-1))
    2. PRINT “Overflow Condition”
    3. Else
    4. IF(Front == -1)
    5. Front = Rear =0
    6. Queue[Rear] = Data
    7. Priority[Rear] = Priority
    8. ELSE IF(Rear ==N-1)
    9. FOR i=Front;i<=Rear;i++)
    10. FOR(i=Front;i<=Rear;i++) 
    11. Q[i-Front] =Q[i]
    12. Pr[i-Front] = Pr[i]
    13. Rear = Rear-Front
    14. Front = 0
    15. FOR(i = r;i>f;i–)
    16. IF(p>Pr[i])
    17. Q[i+1] = Q[i] Pr[i+1] = Pr[i]
    18. ELSE 
    19. Q[i+1] = data Pr[i+1] = p
    20. Rear++
  • Dequeue()
    1. IF(Front == -1)
    2. PRINT “Queue Under flow condition” 
    3. ELSE
    4. PRINT”Q[f],Pr[f]”
    5. IF(Front==Rear)
    6. Front = Rear = -1
    7. ELSE
    8. FRONT++
  • Print()
    1. FOR(i=Front;i<=Rear;i++)
    2. PRINT(Q[i],Pr[i])

C Program to Implement Max Priority Queue or descending priority Queue (using Ordered Array)

#include<stdio.h>
#define N 20
int Q[N],Pr[N];
int r = -1,f = -1;
void enqueue(int data,int p)//Enqueue function to insert data and its priority in queue
{
	int i;
	if((f==0)&&(r==N-1)) //Check if Queue is full
		printf("Queue is full");
	else
	{
		if(f==-1)//if Queue is empty
		{
			f = r = 0;
			Q[r] = data;
			Pr[r] = p;

		}
		else if(r == N-1)//if there there is some elemets in Queue
		{
			for(i=f;i<=r;i++) { Q[i-f] = Q[i]; Pr[i-f] = Pr[i]; r = r-f; f = 0; for(i = r;i>f;i--)
				{
					if(p>Pr[i])
					{
						Q[i+1] = Q[i];
						Pr[i+1] = Pr[i];
					}
					else
						break;
					Q[i+1] = data;
					Pr[i+1] = p;
					r++;
				}
			}
		}
		else
		{
			for(i = r;i>=f;i--)
			{
				if(p>Pr[i])
				{
					Q[i+1] = Q[i];
					Pr[i+1] = Pr[i];	
				}
				else
					break;
			}
			Q[i+1] = data;
			Pr[i+1] = p;
			r++;
		}	
	}

}
void print() //print the data of Queue
{
int i;
	for(i=f;i<=r;i++)
	{
		printf("\nElement = %d\tPriority = %d",Q[i],Pr[i]);
	}
}
int dequeue() //remove the data from front
{
	if(f == -1)
	{
		printf("Queue is Empty");
	}	
	else
	{
		printf("deleted Element = %d\t Its Priority = %d",Q[f],Pr[f]);
		if(f==r)
			f = r = -1;
		else
			f++;
	}
}
int main()
{
	int opt,n,i,data,p;
	printf("Enter Your Choice:-");
	do{
		printf("\n\n1 for Insert the Data in Queue\n2 for show the Data in Queue \n3 for Delete the data from the Queue\n0 for Exit");
		scanf("%d",&opt);
		switch(opt){
			case 1:
				printf("\nEnter the number of data");
				scanf("%d",&n);
				printf("\nEnter your data and Priority of data");
				i=0;
				while(i<n){
					scanf("%d %d",&data,&p);
					enqueue(data,p);
					i++;
				}
				break;
			case 2:
				print();
				break;
			case 3:
				 dequeue();
				break;
			case 0:
				break;
			default:
				printf("\nIncorrect Choice");

		}
	}while(opt!=0);
        return 0;
}

Output

Priority Queue Application

Some of the applications of a priority queue are:

  • Dijkstra’s algorithm
  • for implementing stack
  • for load balancing and interrupt handling in an operating system
  • for data compression in Huffman code
Share
Raj Tuladhar

Raj Tuladhar

learning everything from everywhere!!

%d bloggers like this: