4

My problem is that I have a queue of objects. Each object will be evaluated and will be given a priority.

I thought about a PriorityQueue or TreeSet as both are sorted. The problem is that the priority of each object changes regularly. The named data structures can't handle this scenario.

One possible way may be implementing a heap structure with an increase key function.

Searching the internet I didn't find anything that suits this problem. Oh I should mention that the data structure will have a high throughput.

So I search for something with a good performance like Big O log(n) and below for standard operation.

Timo
  • 2,212
  • 2
  • 25
  • 46
CRC
  • 185
  • 7
  • 3
    Have you looked at [this](http://stackoverflow.com/questions/2288241/priority-queue-with-dynamic-item-priorities) question? How about [this](http://stackoverflow.com/questions/450180/a-priority-queue-which-allows-efficient-priority-update) one? – dramzy Aug 12 '15 at 14:10
  • Yeah I have to take a closer look at the second one but it seems not really matching. I saw the first one and the problem is that reinsering the Object causes processing time of big O n+log n. And if you can change the order dynamic it may be possible to achieve this faster. – CRC Aug 12 '15 at 14:51
  • A priority queue is not typically sorted. In fact, you can't say for certain anything about the order of items in the queue. All you know is that when you ask for an item, the one you get will be the smallest (with "smallest" defined by the queue's comparison function). – Jim Mischel Aug 12 '15 at 15:56
  • @CRC Thr approach linked in the first question should work in time O(log n) per update, since a BST insert or remove takes time O(log n). – templatetypedef Aug 12 '15 at 16:29

0 Answers0