[boost] Re: Dynamic Priority Queues

From: Dietmar Kuehl (dietmar.kuehl_at_[hidden])
Date: 1999-06-23 07:59:26

Hi,
At 16:39 22.06.99 -0700, Reid Sweatman wrote:
>I hope this isn't too off-topic for this list, but I was wondering whether
>anyone had given any thought to (or knew of an implementation of) a dynamic
>priority queue template.

I have implementations for Fibonacci-, d- (with d being a template parameter
defaulting to 2), and Radix-Heaps basically ready but they still need more
thorough testing and documentation. In particular, I have only tested them
using egcs (a relatively recent snapshot on a Linux machine) and I currently
don't have any other decent compiler available. I think I could submit the
stuff to the boost library, if somebody can report successful testing on one
or better more different platforms (of course, if there are some bugs, I will
try to remove them).

These classes all have the same interface which is mainly an extension of the
interface of 'std::priority_queue' (not exactly, because eg. 'push()' returns
something different than 'void'): Methods 'increase()', 'decrease()', and
'change()', modifying the key of an object, and 'remove()' to remove an
element are added. What is currently missing are methods 'begin()' and 'end()'
yielding const-iterators for logical inspectability (that is, the contents of
a priority queue is part of its logical state which should be accessible to
clients; this also applies to queues and stacks). However, with the current
interface it is possible to inspect the contents of the heap, although this
uses non-STL iterators, namely iterators suitable to traverse trees.

The classes are written to be submitted to the boost library. However, I just
haven't come around to put them together, clean them up, and submit them. If
anybody is interested in testing the heap implementations such that I can
submit them to the Boost library, I would really appreciate this help. Just
sent me a corresponding e-mail.

Dietmar

------------------------------------------------------------------------

eGroups.com home: http://www.egroups.com/group/boost
http://www.egroups.com - Simplifying group communications