- log-time insertion of elements.
- Constant time popping of the front. (Actually, I can live with log-time here.)
- The ability to reprioritize a single item in log time, based on the item itself.
- Priorities stored with the elements (rather than calculated by a comparator).
- Ability to put items into the queue without adding special "helper" fields.
Item 3 is what makes things interesting...for a lot of priority queue algorithms, the algorithm is only fast if you can reprioritize just a few affected other items without going over the entire queue. (Doing an entire-queue operation will typically give you N-squared time, because you hit the entire queue to reprioritize every time you process a single item.)
There are two ways I've used to do this:
- If I store the priority in the item itself (violates the last two points), I can just insert the items into an STL multi-map by priority. To reprioritize an item, I find it by doing an equal_range query on its current priority, erase it, then reinsert it at the new priority.
- To meet all the point, I use a map from priority to item, but then maintain a separate "back-link" map from items to iterators into the original map. This gives me the ability to find an item by value and remove it from the priority queue and reinsert it.