Re: How to choose a Data-Structure for a Priority Queue ?

On Wed, 11 Nov 2009 13:39:42 +0000, Ben Bacarisse wrote:


One trick that might work for you is to use a counter. You increment it
every time you add an item and you store it with the priority p to form
a pair (p, c). This forms the real priority you use for organising your
heap:

(p, c) < (p', c') if p < p' but if p == p' use c < c'

This extra storage may be show-stopper, and you may not be able to live
with the fact that you can't reset the counter without some O(N) work,
but it is worth considering.


That is new one. How is my idea compared to it which takes advantage of
the fact that items are added according to the priority:


when we add an item with duplicate priority we add it just after the
original one, so a block of linked list queue will look like this:

(p0, item1) -> (p1, item2) -> (p1, item3) -> (p4, item4)

Since we always remove the elements from the head, we are always going to
remove that oldest one.

During addition of a duplicate when we come across the original we can
check its next pointer to if next one has same priority, and then next
one, till we get a different priority. That way we will need only 2 extra
pointers but not extra O(N) search.



If not, use multiple non-priority queues (plain FIFOs) organised into a
heap as has already been suggested by Willem.


I don't think its good idea because I may or may not have duplicates,
even if I have them, still then there could be million of different
priorities and I don't think making millions of different queues is a
good idea even when they are going to be deleted soon.




--
www.lispmachine.wordpress.com
my email is @ the above blog.

.

Relevant Pages

  • Re: How to choose a Data-Structure for a Priority Queue ?
    ... You say there will typically be about 10,000 elements in the queue, so ... but priority queues rarely work like that. ... duplicate and 2nd if duplicate is there then add it after that duplicate ... and any sort of strange requirements that pop ...
    (comp.programming)
  • Re: How to choose a Data-Structure for a Priority Queue ?
    ... You say there will typically be about 10,000 elements in the queue, so ... to find the insertion point, but priority queues rarely work like that. ... duplicate and 2nd if duplicate is there then add it after that duplicate ...
    (comp.programming)
  • Re: How to choose a Data-Structure for a Priority Queue ?
    ... priority and person with minimum priority will always be removed first." ... duplicate and 2nd if duplicate is there then add it after that duplicate ... what programming language are you using? ... You all think I'm paranoid, ...
    (comp.programming)
  • Re: How to choose a Data-Structure for a Priority Queue ?
    ... You say there will typically be about 10,000 elements in the queue, so ... to find the insertion point, but priority queues rarely work like that. ... duplicate and 2nd if duplicate is there then add it after that duplicate ...
    (comp.programming)
  • Re: stuck in Infinite-loop
    ... To add a duplicate element into the Priority Queue ... struct pq_element* next; ... struct pql* PQL_init; ...
    (comp.lang.c)