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.
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.
|, 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.