Priority Queues in data structure

A priority queue is a data structure in which each element is assigned a priority. The priority of the element will be used to determine the order in which the elements will be processed. The general rules of processing the elements of a priority queue are

  • An element with higher priority is processed before an element with a lower priority.
  • Two elements with the same priority are processed on a first-come-first-served (FCFS) basis

Implementation of a Priority Queue

There are two ways to implement a priority queue. We can either use a sorted list to store the elements so that when an element has to be taken out, the queue will not have to be searched for the element with the highest priority or we can use an unsorted list so that insertions are always done at the end of the list. Every time when an element has to be removed from the list, the element with the highest priority will be searched and removed. While a sorted list takes O(n) time to insert an element in the list, it takes only O(1) time to delete an element. On the contrary, an unsorted list will take O(1) time to insert an element and O(n) time to delete an element from the list

Practically, both these techniques are inefficient and usually a blend of these two approaches is adopted that takes roughly O(log n) time or less

Linked Representation of a Priority Queue

In the computer memory, a priority queue can be represented using arrays or linked lists. When a priority queue is implemented using a linked list, then every node of the list will have three parts: (a) the information or data part, (b) the priority number of the element, and (c) the address of the next element. If we are using a sorted linked list, then the element with the higher priority will precede the element with the lower priority

Priority queue

program to implement a priority queue

#include <stdio.h>
#include <malloc.h>
#include <conio.h>
struct node
{
int data;
int priority;
struct node *next;
}
struct node *start=NULL;
struct node *insert(struct node *);
struct node *delete(struct node *);
void display(struct node *);
int main()
{
int option;
clrscr();
do
{
 printf("\n *****MAIN MENU*****);
 printf("\n 1. INSERT");
 printf("\n 2. DELETE");
 printf("\n 3. DISPLAY");
 printf("\n 4. EXIT");
 printf("\n Enter your option : ");
 scanf( "%d", &option);
switch(option)
 {
 case 1:
 start=insert(start);
break;
 case 2:
 start = delete(start);
break;
 case 3:
 display(start);
break;
 }
}while(option!=4);
}
struct node *insert(struct node *start)
{
int val, pri;
struct node *ptr, *p;
ptr = (struct node *)malloc(sizeof(struct node));
printf("\n Enter the value and its priority : " );
scanf( "%d %d", &val, &pri);
ptr–>data = val;
ptr–>priority = pri;
if(start==NULL || pri < start–>priority )
{
 ptr–>next = start;
 start = ptr;
}
else
{
 p = start;
while(p–>next != NULL && p–>next–>priority <= pri)
 p = p–>next;
 ptr–>next = p–>next;
 p–>next = ptr;
}
return start;
}
struct node *delete(struct node *start)
{
struct node *ptr;
if(start == NULL)
{
 printf("\n UNDERFLOW" );
 return;
}
else
{
 ptr = start;
 printf("\n Deleted item is: %d", ptr–>data);
 start = start–>next;
 free(ptr);
}
return start;
}
void display(struct node *start)
{
struct node *ptr;
ptr = start;
if(start == NULL)
 printf("\nQUEUE IS EMPTY" );
else
{
 printf("\n PRIORITY QUEUE IS : " );
while(ptr != NULL)
 {
 printf( "\t%d[priority=%d]", ptr–>data, ptr–>priority );
 ptr=ptr–>next;
 }
}
}

Output

*****MAIN MENU*****
1. INSERT
2. DELETE
3. DISPLAY
4. EXIT
Enter your option : 1
Enter the value and its priority : 5 2
Enter the value and its priority : 10 1
Enter your option : 3
PRIORITY QUEUE IS :
10[priority = 1] 5[priority = 2]
Enter your option : 4

Leave a Comment