[boost] Re: Dynamic Priority Queues

From: Reid Sweatman (reids_at_[hidden])
Date: 1999-06-24 17:09:35

Sounds like you've written pretty much just what I described.  I'd like to
volunteer to test it for you on VC++ 5 and 6, W98/NT, but that will have to
wait a couple of months, because the project I need them for is into
critical crunch time right now, with yours truly being the most critical
crunchee, unfortunately.  If you still want help with it in a couple of
months, I'd be glad to pitch in.  I'd also like to just look at it now, if
you're ready to let it be seen.  If you'd like, I'll sign an NDA.  I'm on a
commercial product right now, but wouldn't use your code for such a thing
until you released it into the public domain (or published to Boost.

I knew the "iterator" for random access couldn't be a true STL iterator, but
I'm one of those people who'd like to see the STL expanded to include other
types of containers than ordered and non-ordered linear ones.  Trees and
DAG's, mainly.  That would make life so much simpler.  Except for the poor
suckers who have to write and debug the things <g>.

I've never heard of Fibonacci heaps before, but can sort of guess what they
must be.  Can you point me to a good source on heaps in general?  Either a
book (in English, because my Deutsch is pretty weak <g>), or a web site or
paper.  Thanks.

> -----Original Message-----
> From: Dietmar Kuehl [mailto:dietmar.kuehl_at_[hidden]]
> Sent: Wednesday, June 23, 1999 5:59 AM
> To: 'boost_at_[hidden]'
> Subject: [boost] Re: Dynamic Priority Queues
> 
> 
> 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
> 
> --------------------------------------------------------------
> ----------
> Make the News Come to you! FREE email newsletters sent directly to 
> your in-box USAToday, Forbes, Wired, and more. Sign-up NOW!
> http://clickhere.egroups.com/click/316
> 
> 
> eGroups.com home: http://www.egroups.com/group/boost
> http://www.egroups.com - Simplifying group communications
> 
> 
> 
> 

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

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