Priority Queues using std::priority_queue

Priority Queue with Dynamic Priorities

Can I update the priority of an element already in the priority queue?

Illustration representing computer hardware

The standard std::priority_queue in C++ does not provide a direct way to update the priority of an element that is already in the queue. Once an element is inserted into the priority queue, its priority is fixed and cannot be modified.

However, if you need to update the priority of an element dynamically, you can achieve this by removing the element from the priority queue, updating its priority, and then reinserting it into the queue.

Here's an example of how you can update the priority of an element in a priority queue:

#include <iostream>
#include <queue>
#include <vector>

struct Element {
  int value;
  int priority;
};

struct CompareElement {
  bool operator()(const Element& e1,
    const Element& e2) {
    return e1.priority < e2.priority;
  }
};

int main() {
  std::priority_queue<Element,
    std::vector<Element>, CompareElement> pq;

  pq.push({10, 2});
  pq.push({20, 1});
  pq.push({30, 3});

  int elementToUpdate = 20;
  int newPriority = 4;

  std::vector<Element> tempElements;

  while (!pq.empty()) {
    Element current = pq.top();
    pq.pop();

    if (current.value == elementToUpdate) {
      current.priority = newPriority;
    }

    tempElements.push_back(current);
  }

  for (const auto& element : tempElements) {
    pq.push(element);
  }

  while (!pq.empty()) {
    std::cout << pq.top().value
      << " (Priority: "
      << pq.top().priority << ")\n";
    pq.pop();
  }
}

In this example, we define a struct Element that represents an element with a value and a priority. We also define a custom comparator CompareElement that compares elements based on their priority.

We create a priority queue of Element objects and insert some initial elements. To update the priority of an element, we specify the elementToUpdate and the newPriority.

We create a temporary vector tempElements to store the elements while we update the priority. We iterate over the priority queue, popping each element. If the current element's value matches the elementToUpdate, we update its priority to newPriority. We then push the element into the tempElements vector.

After processing all elements, we reinsert the elements from tempElements back into the priority queue using a loop.

Finally, we print the elements in the updated priority queue to verify the changes.

The output of this code will be:

20 (Priority: 4)
30 (Priority: 3)
10 (Priority: 2)

As you can see, the priority of the element with value 20 has been updated to 4, and the priority queue maintains the correct order based on the updated priorities.

Keep in mind that this approach has a time complexity of O(n log n), where n is the number of elements in the priority queue, as we need to remove all elements and reinsert them. If you need to perform frequent priority updates, you might consider using a different data structure, such as a heap or a tree-based priority queue, that supports efficient priority updates.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved