Priority Queues using std::priority_queue

# Priority Queue with Dynamic Priorities

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

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.

This Question is from the Lesson:

### Priority Queues using std::priority_queue

Learn how to access objects based on their importance, and how to customise how that priority is determined

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

This Question is from the Lesson:

### Priority Queues using std::priority_queue

Learn how to access objects based on their importance, and how to customise how that priority is determined

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.