Re: [boost] 'stable' priority queue

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2001-04-17 07:55:40

Hi,
--- Geurt Vos <G.Vos_at_[hidden]> wrote:
> Is there any interest in a stable priority queue?

I don't know whether there is any interest, however, I can comment on
the technical issues of the implementation of a stable priority queue.

> This problem seems to come up so now and then
> at several places. For what I know, also boost
> doesn't provide a stable one (right?).

For good reasons the provided priority queues do not support this
option. Basically, the good reason is this: There are two approaches,
only one of them being viable:

- Find elements with the same priority in the priority queue and use a
  list or something similar to guarantee stability. This is rather
  inefficient and thus not viable: Priority queues are not order by
  their priority but rather according to a certain "heap property"
  which makes it efficient to access the element with a highest (or
  lowest priority).

- Add a time stamp to the element and make it part of the priority key:
  If the priority is identical, compare the time stamp. This is the way
  to go and a viable approach with all priority queues I have provided.
  It desired, it should be reasonably simple to create a wrapper which
  aides in doing so.

> I do realize the functionality is quite easily
> emulated with a std::multiset, which could be
> reason enough to not add the priorty queue
> 'wrapper'.

It is likely that this approach is much slower than the other approach:
I haven't measured the difference and can only guess but the idea of
typical priority queues is to store the data in a structure well suited
for the heap operations. In any case, the theoretical complexity of the
approach using a multi-set is worse than the complexity of the priority
queues (may be it is identical for some but definitely worse for
Fibonacci heaps which happen, however, to be practically slighlty
inferior than d-heaps).

=====
<mailto:dietmar_kuehl_at_[hidden]>
<http://www.dietmar-kuehl.de/>

__________________________________________________________________
Do You Yahoo!?
Gesendet von Yahoo! Mail - http://mail.yahoo.de