Program for Priority Queue Insertion and Deletion in C++

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.

Priority Queue Insertion and Deletion in C++

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)

Insertion operation in priority queue

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)

Deletion in priority queue

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)