C++

Forum

 
How to get std::priority_queue to update dynamically when element priorities change?

ElusiveTau (152)
Suppose you have a custom type, Foo, whose Num member is used to determine priority in a priority_queue:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
struct Foo
{
    string Name = "";
    int Num = 0;

    Foo() {}
    Foo(string name, int num) : Name(name), Num(num) {}

    friend bool operator<(const Foo& left, const Foo& right);
    friend ostream& operator<<(ostream& os, const Foo& foo);
};

bool operator<(const Foo& left, const Foo& right)
{
    return (left.Num < right.Num);
}

ostream& operator<<(ostream& os, const Foo& foo)
{
    return (os << "Foo(" << foo.Name << "," << foo.Num << ")");
}


Q1. Is it possible to modify the priority of elements already stored inside a priority_queue? If so, does the priority_queue rearrange its elements internally, automatically, to account for the changed priority values? 

1
2
3
4
5
6
7
8
9
10
11
 
    Foo alice("Alice", 1);
    Foo bob("Bob", 2);
    Foo carl("Carl", 3);

    // Copies of Foo objects
    vector<Foo> v1{alice, bob, carl};
    priority_queue<Foo> pq1(v1.begin(), v1.end()); // Gets copies of alice, bob, carl

    alice.Num = 5; // Suppose the value used to determine priority has changed

    // Want pq1 to internally update so new ordering is Alice -> Carl -> Bob


Q2. The code above doesn't work because pq1 gets a copy of those three Foo objects. Is there a way to declare priority_queue so that it stores alias of the alice, bob, carl objects?

I thought about using Foo pointers:
1
2
3
4
5
6
7
 
    // Reference to Foo objects; pointer comparison is used
    vector<Foo*> v2{&alice, &bob, &carl};
    priority_queue<Foo*> pq2(v2.begin(), v2.end());
    for (; !pq2.empty(); pq2.pop())
    {
        cout << *pq2.top() << " ";
    }

... but priority_queue<Foo*> ignores my operator< definition (which compares the Num members of two Foo object) and instead uses pointer-comparison, which is undesirable.

Q3. Is "dynamically update" the right phrase to describe the behavior of containers whose internal structure automatically updates whenever one of the object it stores gets modified? Disjoint Sets is another data structure that would need to dynamically update this way.
ElusiveTau (152)
Of course, one could just reinitialize another priority_queue from one that already exists. But this could potentially involve a lot of expensive copies for no real benefit.

For example, say you want to have a priority queue that stores a fixed-sized collection of elements -- no new elements will be added or removed but element priorities, tied to their state, can change.

[1],[2] says std::priority_queues don't allow you to modify priorities. So it seems you need to implement your own container with this feature. Such a priority queue would need some way to know that one of its stored objects has been updated. But a container's dependency on its object seems odd since the container generally shouldn't care about what it stores.

[1] SO: priority_queue with dynamic priorities
https://stackoverflow.com/a/2921571/5972766

[2] SO: How to update elements inside a std::priority_queue?
https://stackoverflow.com/a/42608353/5972766

SO: How to do an efficient priority update in STL priority queue?
https://stackoverflow.com/questions/649640/how-to-do-an-efficient-priority-update-in-stl-priority-queue

SO: Updating Priority Queue Order On Element Changes
https://stackoverflow.com/questions/55909925/updating-priority-queue-order-on-element-changes
Last edited on
mbozzi (3932)
std::priority_queue is implemented as a binary heap within a container type of your choice. Problem is, it's too inflexible to be useful on its own. It's more viable to maintain the heap invariant in a container by hand. The standard library has std::push_heap and friends to do most of the work, so it's not so bad to implement.
https://en.cppreference.com/w/cpp/algorithm/push_heap
That being said, while writing this post, I learned that priority_queue (and the other container adapters) makes the underlying container object accessible as a protected member, which implies it might be viable to use priority_queue as a base class in your case, and maybe mine too. I'm not sure though, since I haven't had time to think about it.

Q1. Is it possible to modify the priority of elements already stored inside a priority_queue? If so, does the priority_queue rearrange its elements internally, automatically, to account for the changed priority values?
No, you'd need to restore the heap invariant after the change by yourself. The fix-up process could call std::make_heap on the underlying container.

Q2. The code above doesn't work because pq1 gets a copy of those three Foo objects. Is there a way to declare priority_queue so that it stores alias of the alice, bob, carl objects?
Yes - store pointers inside the priority queue as you wrote, but also specify a custom comparator that compares the pointed-to objects.

Q3. Is "dynamically update" the right phrase to describe the behavior of containers whose internal structure automatically updates whenever one of the object it stores gets modified? Disjoint Sets is another data structure that would need to dynamically update this way.
I don't know if there's a term for this. Even a sorted array can't magically fix itself up when the data changes out-of-band.

[1],[2] says std::priority_queues don't allow you to modify priorities. So it seems you need to implement your own container with this feature. Such a priority queue would need some way to know that one of its stored objects has been updated. But a container's dependency on its object seems odd since the container generally shouldn't care about what it stores.
You can do this by requiring the user to go through the priority queue's interface to get write access to elements in the data structure. Knowing which element might have changed (and its new relationship with the other elements) is enough to fix-up the heap invariant.
Last edited on
coder777 (8444)
Q1. Is it possible to modify the priority of elements already stored inside a priority_queue? If so, does the priority_queue rearrange its elements internally, automatically, to account for the changed priority values?
No, I can't think of any kind of container that does this (mostly unwanted) kind of magic.

Q2. The code above doesn't work because pq1 gets a copy of those three Foo objects. Is there a way to declare priority_queue so that it stores alias of the alice, bob, carl objects?
No, a container stores the elements not the references. It would be way to dangerous. I would not recommend pointer either.

If you just want the elements be sorted use a container like vector. You can apply std::sort/stable_sort any time when the elements are changing.
Last edited on
jonnin (11437)
what you are talking about is a sorted container that is smart enough to trigger a re-sort when its data is modified. Its easy to write an object where your modifier (the function that lets you change the priority of some random access element) triggers a sort afterwards. Be sure to lock the data so that the priority CANNOT be modified ANY OTHER WAY than by this function (and any peers if you need multiple) that triggers the re-sort on the whole object. I don't think this is strange or unwanted at all (??) if the entire premise of your object is that it does exactly that.

So, perhaps if I were doing it, I would have one simple small object that does nothing but maintain a sorted list of pointers to items based off a provided key (that may or may not be part of the item object). A vector of standard pair to <T*, int> where T is your template type (item class). And all its going to let you do is add/remove a full entry (item, key) or modify an item(return its pointer, if you want this, this could be undesirable!) or modify a key (triggers the resort). You can build your priority queue from this with a little extra logic (mainly, and this is VERY IMPORTANT, you need to stable-sort the data or sort it off a second, hidden key (timestamp when added to the queue, perhaps) so that it REALLY IS A QUEUE. If you do not do this right, items that have the same priority may come out of the queue in random order, rather than FIFO due to the sort-scrambling of the order!). You have to decide if you want modification of a priority/key to reposition the item in the queue (back of the line at its new priority) or not (keep its original insertion order).
Last edited on
Topic archived. No new replies allowed.