7

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?

Improve this question
5
  • 1
    Can the changes in priority go both ways (up and down) or just one way? Commented Dec 28, 2012 at 9:03
  • @Thilo They can change both ways. Commented Dec 28, 2012 at 9:05
  • Heap would be a good choice. Commented Dec 28, 2012 at 9:17
  • You cannot choose a better metrics? How do you know which items needed to be requeue? I means how do you track them. Commented Dec 28, 2012 at 10:10
  • @hwlau : The items are connected in a graph, and when I process one item, I effectively make a local change in the graph, which changes the metric of the item's neighbours. Commented Dec 28, 2012 at 11:57

4 Answers 4

Reset to default
3

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

You can not achieve the complexity you are asking for, as when updating elements the complexity should also depend on the number of updated elements.

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

Improve this answer

Comments

0

A Priority queue is exactly for this. You can implement it, for example, by using max-heap.

Improve this answer

3 Comments

How would you implement the requeue operation efficiently in such a heap?
Heap is a binary search tree. The deletion is O(logn) on average and O(n) in the worst case. Insertion to the heap is O(logn)
@icepack A heap is not a binary search tree. It is especially not well-suited for searching on the items stored (as opposed to the priororities of them), which is what is needed for a requeue operation.
0

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf describes increaseKey(), decreaseKey() and remove() operations. This would let you do what you want. I haven't figured out if the C++ stdlib implementation supports it yet.

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.