What data structure is used for "dynamic" queuing?

Question

I am looking for a data structure to support some sort of priority queue. The idea is this. I need to process several elements sequentially, and at any given time I know the “best” thing to do next (based on some metric). The fact is that processing an element changes the metric for several other elements, so a static queue does not do this trick.

In my problem, I know which elements should update their priorities, so the data structure I'm looking for should have methods

• enqueue (element, priority)
• Dequeue ()
• requeue (item, new_priority)

Ideally, I would like to request O (log n) time. Any ideas?

Answer 1

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

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

• Call dequeue()
• If the ignore bit in the element is true, return to 1, otherwise return the identifier of the element.

The algorithm for the modified enqueue is as follows:

• Call Queue (item, priority)
• Visit the neighboring nodes of the v element on the graph one at a time
  • change the ignore bit to true since the current related item in the queue matches v
  • enqueue (v, new_priority (v))
  • change the node v connection to the new selected items.
  • num_ignore ++
• If the ignore element number ( num_ignore ) is greater than the number of the element not ignored, rebuild the priority queue
  • dequeue all elements, save and then enqueue again do not ignore elements

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

Answer 2

A Priority queue is just for that. You can implement it, for example, using max-heap .

Answer 3

You cannot achieve the required complexity, since when updating elements, the complexity should also depend on the number of updated elements.

However, if we assume that the number of updated elements in this step is p , most typical heap implementations will perform for O(1) complexity to get the max-element value, O(log(n)) for deque, and O(p * log(n)) for update operations. I would personally go to the binary heap, since it is quite easy to implement and will work on what you are asking for.

Answer 4

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf describes the operations of increasing Key (), reduceKey () and remove (). This will allow you to do what you want. I have not figured out yet if the C ++ implementation of stdlib supports it.

Also, the version of http://theboostcpplibraries.com/boost.heap seems to support update () for some subclasses, but I haven't found the full link yet.