# 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. ## 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)`