Which data-structure to use for "dynamic" priority queueing?

Question

I am looking for a datastructure to support a kind of advanced priority queueing. The idea is as follows. I need to sequentially process a number of items, and at any given point in time I know the "best" one to do next (based on some metric). The thing is, processing an item changes the metric for a few of the other items, so a static queue does not do the trick.

In my problem, I know which items need to have their priorities updated, so the datastructure I am looking for should have the methods

• enqueue(item, priority)
• dequeue()
• requeue(item, new_priority)

Ideally I would like to requeue in O(log n) time. Any ideas?

Answer 1

There is an algorithm with time complexity similar to what you required, but it runs O(log n) only on average time, if it is what you needed. In this algorithm, you can use existing priority queue without the requeue() function.

Assuming you have a connection between the nodes in your graph and the elements in the priority queue. Let the element of the priority queue also store an extra bit called ignore. The algorithm for the modified dequeue runs as follow:

1. Call dequeue()
2. If the ignore bit in the element is true, go back to 1, otherwise return the item id.

The algorithm for the modified enqueue runs as follow:

1. Call enqueue(item, priority)
2. Visit neighbor nodes v of the item in the graph one by one
   • change the ignore bit to true for the current linked element in the queue correspond to v
   • enqueue(v, new_priority(v))
   • change the connection of the node v to the new enqueued elements.
   • num_ignore++
3. If the number of ignore element (num_ignore) is more than the number of non-ignore element, rebuild the priority queue
   • dequeue all elements, store, and then enqueue only non-ignore elements again

In this algorithm, the setting of ignore bit takes constant time, so you basically delay the O(log n) "requeue" until you accumulate O(n) ignore elements. Then clear all of them once, which takes O(n log n). Therefore, on average, each "requeue" takes O(log n).