Program for Priority Queue Insertion and Deletion in C++

February 14, 2022

Priority Queue Insertion and Deletion in C++

Here, in this page we will discuss the program for Priority Queue Insertion and Deletion in C++ programming language. We will discuss an efficient way for inserting and deleting an element in queue.

What is Priority Queue?

A priority is basically an extension of the general queue. A major difference is that dequeuing happens based on the priority of each item in the queue.

Types of Priority Queue :

Max Priority Queue – A larger priority value means higher priority
Min Priority Queue – A smaller priority value means lower priority

Operations on Priority Queue

Different operations that can be performed on priority queue are given below,

enqueue()
dequeue()
peek()/top()

Let’s discuss each operations in brief,

enqueue()

Adding a new item to the Queue Data Structure, in other words Enqueue new item to Queue If Queue is full, then it is said to be in an overflow condition.
When we require to add an element and its priority to the queue we perform enqueue() operation.
Enqueue() operation is synonymous of insertion in a data structure Queue.

Time-Complexity of enqueue() operation

The time complexity for inserting an element in the priority queue is O(1)

dequeue()

Delete a item from a Queue, Deletion based on priority, highest priority element deleted first.In other words Dequeue item from Queue If queue is empty then it is said to be in an underflow condition.
When we require to delete an element and its priority from the queue we perform dequeue() operation.
dequeue() operation is synonymous of deletion in a data structure Queue.

Time-Complexity of dequeue() operation

The time complexity for deleting an element in the priority queue is O(N)

peek()/top()

This function returns the element with highest priority in the given priority queue.

Traverse the entire priority queue and find the element with the highest priority and return its index.
In the case of multiple elements with the same priority, find the element with the highest value having the highest priority.

Time-Complexity of peek() operation

The time complexity for finding the element with highest priority is O(N)

Code in C++

#include<iostream>
#include<limits.h>
#define MAX 100
using namespace std;

// struct to hold data and priority of any item in priority queue
struct item
{
  int data;
  int priority;
};				

// array of type struct item
// example rather than int array[] we have item array[]
// item is a struct that holds data and priority
item pq[MAX];	

// denotes where the last item in priority queue is
// initialized to -1 since no item is in queue
int idx = -1;

bool isEmpty ()
{
  return idx == -1;
}

bool isFull ()
{
  return idx == MAX - 1;
}

// enqueue just adds item to the end of the priority queue | O(1)
void enqueue (int data, int priority)
{
  if (!isFull ())
    {
      // Increase the index
      idx++;
      // Insert the element in priority queue
      pq[idx].data = data;
      pq[idx].priority = priority;
    }
}	

// returns item with highest priority
// NOTE: Low priority number means higher priority | O(N)
int peek ()
{
  int maxPriority = INT_MAX;
  int indexPos = -1;	
  
  // Linear search for highest priority
  for (int i = 0; i <= idx; i++) {
             // If two items have same priority choose the one with 
             // higher data value
             if (maxPriority == pq[i].priority && indexPos > -1 && pq[indexPos].data < pq[i].data){ 
                 maxPriority = pq[i].priority; indexPos = i;
             } 

             // note low priority number means higher priority
             // ex: Two processes P1 - 1 priority and P2 - 5 priority 
             // P1 will get executed first, thus comes out of ready queue first
             else if (maxPriority > pq[i].priority){
	          maxPriority = pq[i].priority;
	          indexPos = i;
	    }
    }				
    
    // Return index of the element where
    return indexPos;
}	

// This removes the element with highest priority
// from the priority queue | O(N)
void dequeue ()
{
  if (!isEmpty ())
    {
      // Get element with highest priority
      int indexPos = peek ();	
      
      // reduce size of priority queue by first
      // shifting all elements one position left
      // from index where the highest priority item was found
      for (int i = indexPos; i < idx; i++)
	  {
	     pq[i] = pq[i + 1];
	  }		
	  // reduce size of priority queue by 1
      idx--;
    }
}

void display ()
{
  for (int i = 0; i <= idx; i++)
    {
      cout << "(" << pq[i].data << ", " << pq[i].priority << ")\n";
    }
}

// Driver Code
int main ()
{
  // To enqueue items as per priority
  enqueue (10, 1);
  enqueue (20, 3);
  enqueue (30, 4);
  enqueue (40, 5);
  enqueue (1000, 2);
  
  cout << "Before: " << endl;
  display (); 
  
  // Dequeue the top element
  dequeue (); // 10 dequeued
  dequeue (); // 1000 dequeued 
  
  cout << "\nAfter: " << endl;
  display ();
  return 0;
}

Output :

Before :

(10, 1)
(20, 3)
(30, 4)
(40, 5)
(1000, 2)


After :

(20, 3)
(30, 4)
(40, 5)