priority queue in C++?

Yep stl has one.

There's std::priority_queue, but it doesn't support priority changes (I can't really imagine what the parameters of that function would look like).

You might be interested in std::make_heap and its ilk (or write a percolation function yourself) if you need priority changes.

There seems to be a priority_queue class in #include . It does not seem to allow changing the priority of the queue elements. And iteration of the elements is also not allowed.

One can always use the STL algorithms for heaps and construct a heap for priority queue handling.

Quote:

Original post by ToohrVyk You might be interested in std::make_heap and its ilk (or write a percolation function yourself) if you need priority changes.

On second thoughts, only decrease_key is needed. Increasing is not necessary. This method should be called by the user when he knows that the
expression comparator(element) has changed value due to a manipulation of the element. He should pass something that compares equal with the element, e.g. a copy of it, to the method (iterators won't work well because of the potential constant relocation of objects):
void decrease_key(const value_type& element);

Quote:

Original post by all_names_taken On second thoughts, only decrease_key is needed. Increasing is not necessary. This method should be called by the user when he knows that the expression comparator(element) has changed value due to a manipulation of the element. He should pass something that compares equal with the element, e.g. a copy of it, to the method (iterators won't work well because of the potential constant relocation of objects): void decrease_key(const value_type& element);

No, there is no standard container that has those properties. A priority queue is a queue (access only at the front is allowed). It does not allow random or sequential access to its elements (define sequential access to elements of a heap if you dare, and how random access would work if you can) and it does not allow varying priority values.

Your best bet is to start by copying the std::priority_queue implementation from you favorite standard library and reimplement the addtional functionality using the std::heap_* functions.

Use std::multimap ?

Push = O(log n) (insert)
Pop = O(log n) (begin, erase)
Change priority = O(log n) (erase, insert)
Construct from iterator pair O(n) = Not entirely sure what you mean here but I suspect that the it'n not O(n) but rather O(n log n)

Quote:

Original post by eq Use std::multimap ? Push = O(log n) (insert) Pop = O(log n) (begin, erase) Change priority = O(log n) (erase, insert) Construct from iterator pair O(n) = Not entirely sure what you mean here but I suspect that the it'n not O(n) but rather O(n log n)

Hmm, that is a pretty neat idea. I needed something similar to the OP when prioritising background loading of terrain tiles, as you often discover you can remove tiles from the queue before they are actually loaded.

Quote:

Original post by all_names_taken Does boost or STL contain any priority queue implementation (I couldn't find one)? It needs to have the methods: - push O(log n) - pop O(log n) - change_priority O(log n) - construct from iterator pair O(n) Or is there any other implementation freely available?

change_priority implies that you also need a way of finding an item, or a way of iterating over all items. Hopefully a find being O(n) is okay.

A fibonacci heap should be able to do change_priority fast. Any good C++ implementations around? Seems like a too big project to implement from scratch for primarily the tool chain of my game.

Quote:

Original post by eq Use std::multimap ? Push = O(log n) (insert) Pop = O(log n) (begin, erase) Change priority = O(log n) (erase, insert) Construct from iterator pair O(n) = Not entirely sure what you mean here but I suspect that the it'n not O(n) but rather O(n log n)

Quoted becuase people seem to be ignoring an excellent solution.

Quote:

Construct from iterator pair O(n) = Not entirely sure what you mean here but I suspect that the it'n not O(n) but rather O(n log n)

I think it's impossible to build any sort of ordered structure with O(log n) access time in less than O(n log n), correct?
Edit: One could argue that it's possible to sort in O(n) time using radix sort so it might be doable.

If the iterator pairs are already sorted then there should be ways of meeting this requirement (not by using std::multimap in any way that I can think of though).

Quote:

Original post by eq Quote: Construct from iterator pair O(n) = Not entirely sure what you mean here but I suspect that the it'n not O(n) but rather O(n log n) I think it's impossible to build any sort of ordered structure with O(log n) access time in less than O(n log n), correct?

You'd think so, but std::make_heap runs in linear time. There are smarter ways to build an ordered collection than "one element at a time". :)

There are various priority queues in libstdc++, the GNU implementation of the standard library, as extensions.
Among others, a fibonacci heap.