











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.


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 priorityMin 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)
Login/Signup to comment