Delete elements in a priority queue in C++ STL [4 methods]

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have presented different ways to delete elements in a priority queue in C++ STL. There are 4 different methods such as pop, clear and much more.

Table of contents:

  1. Introduction to priority queues
  2. Method one (pop())
  3. Method two (remove specific element)
  4. Method three (erase)
  5. Method four (clear)

Introduction to priority queues

A priority queue is a container in C++ STL (Standard Template Library) that allows users to store elements with different priorities. The priority queue automatically arranges elements in a particular order based on the priority. The element with the highest priority in the priority queue always appears at the top. C++ STL provides various functions to manipulate priority queue, including deleting elements. In this essay, we will discuss different ways to delete elements in a priority queue using C++ STL.

The 4 Different ways to delete elements in a priority queue in C++ STL are:

  1. Method one (pop())
  2. Method two (remove specific element)
  3. Method three (erase)
  4. Method four (clear)

Method one (pop())

pop(): The simplest and most common way to delete an element from the priority queue is by using the pop() function. The pop() function removes the top element from the priority queue. It means that the element with the highest priority is deleted from the priority queue. After deleting the top element, the next highest priority element becomes the new top element in the priority queue. An example of using the pop function on a priority queue is shown below:

priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(15);
pq.pop();
cout << pq.top();

The output from the above function is now 10. However, when 10, 5, and 15 were initially pushed into the priority queue, the order went 15, 10, 5. This is the normal priority of integers in a priority queue. Before the pop function, 15 was on top. Once the pop function was used, the highest priority element was removed, resulting in 10 being at the top: 10, 5.

Method two (remove specific element)

There is no specific remove function in the priority queue class. The pop() function is the closest function you can get to removing an element from the priority queue. However, there are ways one can get around to deleting a specific element of their choice from a priority queue. One can store which element they would like to delete in a variable and create a new priority queue. After doing this, one can use a loop to push every element from the original priority queue into the new queue as long as it does not equal the variable which holds the element they want to delete. This whole process can be seen below.

priority_queue<int> pq;
pq.push(5);
pq.push(10);
pq.push(15);
//let's say we want to delete element 10
//create a new priority queue
priority_queue pq_new;
int delete_me = 10;
while (!pq.empty()) {
    if (pq.top() != delete_me) {
        pq_new.push(pq.top());
    }
    pq.pop();
    
}
//the new priority queue holds 15, 5

This is a great way to remove a specific element without doing too much work. This would require an additional O(n) space complexity and would take O(n) time. This is not too bad. There are a couple other ways to delete elements in a priority queue which we will look at next.

Method three (erase)

This method goes along with method two as there is no specific remove element function in the priority queue. Along with creating a new priority queue without the desired element to remove, one can utilize the erase function. Thie method will keep the original priority queue without the element that needs to be deleted. This code can be seen below:

priority_queue<int> pq;
pq.push(30);
pq.push(50);
pq.push(1);
pq.erase(std::find(pq.c.begin(), pq.c.end(), 30));
//that line deletes the element 30 from the priority queue

This ia also a great way to remove a specific element from a priority queue. However, the above methods we have discussed only entail ways to delete one element from a priority queue. That begs the question, what if we would like to delete everything from a priority queue? There happens to be a way to do this as well.

Method four (clear)

This method deletes all elements from the priority queue without deleting the actual structure. The code for this can be seen below:

priority_queue<int> pq;
pq.push(10);
pq.push(40);
cout << pq.size() << endl;
//this outputs 2
pq.clear();
cout << pq.size() << endl;
//this outputs 0

This method as seen, deletes all elements from the priority queue. Overall, there are many different ways that one can delete elements from a priority queue. Whether one wants to delete one element or many, the class provides options to do it all.

There are numerous real world applications of priority queues and the ability to delete elements from the queue serves great purpose. One such application is in a hospital. Patients can be stored in the queue in accordance to their condition. Patients that need help most urgently can be stored at the top and the list goes down. Once a patient is helped, they can simply be popped off the queue. Or, if a patient in the middle of the queue decides to go to a different hospital, one can simply remove them from the queue. A priority queue is very powerful and can help with many different applications.

With this article at OpenGenus, you must have the complete idea of Different ways to delete elements in a priority queue in C++ STL.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.