Your Friend the Priority Queue

One of the things I like about the STL is that it makes easy in C++ higher level data structures that make programs better but would otherwise be too cumbersome to use. For example, when was the last time you coded a red-black tree in C? But std::map is pretty easy.

Here’s my extremely unsound and imprecise definition of a priority queue: a priority queue is a data structure where you can rapidly insert “todo” items, find the most important one, reprioritize an item, and remove a finished item. Ideally I’d like all of these tasks to run in logarithmic time or better.

One way to hack out a priority queue using the STL is like this:

struct my_item;
typedef multimap queue_type;
struct my_item {
queue_type::iterator self;
xint more_stuff;
};

The idea is simple: map already gives us logarithmic time to locate the first item, insert and remove an item. The struct has a pointer to its own iterator allowing it to reprioritize by adding and removing itself, like this:

void reprioritize(my_item * item, float new_prio, queue_type * a_queue)
{
a_queue->erase(my_item->self);
my_item->self = a_queue->insert(queue_type::value_type(new_prio, item));
}

I can’t say that this is terribly good C++ but I can say that it works quite well. An examples of priority queues used to create X-Plane scenery:

We use a greedy algorithm to build our triangulations from elevation data. Basically we find the locatoin on our mesh that is the most wrong and fix it by inserting a new point into our mesh. We then re-evaluate the mesh and fix the next-worst point. We repeat until we’ve added too many points or the worst point isn’t that bad. Here’s where the priority queue comes in: when we insert a point, the error between our local mesh and the ideal elevations change, but only for a few points near the insert. So we want to rapidly reprioritize those points without having to reconsider the others. With a 1.5 million potential points and perhaps a few hundred thousand inserts, the priority queue is critical. With a good priority queue this algorithm takes a few seconds; without it a few hours. (This algorithm comes from a paper - I wish I could find it but I did not record the URL in my code. When I find it I will post a link.)

When should you think priority queue? Well, any time you have to evaluate a whole series of conditions at specific events, and the time of the events is known in advance, a priority queue can help. It may be necessary to replace polling logic (e.g. “is it time to flush the queue now”) with solid predictions (e.g. “I know that this queue is 25 bytes away from being full and that one is 13 bytes from being full”).

The STL provides another approach to priority queues: tucked away in the algorithms section are routines like make_heap, is_heap, push_heap, and pop_heap. A heap is basically an array of data that’s sorted just enough that the smallest item is in front. It’s faster to preserve these relaxed requirements than to do a full sort. I haven’t utilized heaps in my code yet, so I can’t comment on heap vs map performance.