Bug fixes and interface changes for priority queues

From: brianjparker_at_[hidden]
Date: 2001-10-28 07:13:05

I have just uploaded the latest version of the bug fixes and 
interface changes I have made to Dietmar Kühl's priority queue 
classes.

I have used these classes extensively over the past year or so- in 
particular the fibonacci_heap- and, whilst the original 
implementation was not directly useable I have applied several bug 
fixes so that it now correctly handles repeated values etc. I have 
used the Fibonannci heap on huge, randomly accessed data sets (e.g. > 
100000) and it is, AFAIK, totally reliable now. 

I have also generalized the interface e.g. allocator template 
parameters are now available and "pointers" (which I have renamed 
as "trivial_iterators") now allow dereferencing, and there is a meld 
function.
 
Please see boost_ext\libs\heap_fixes\html\index.html for full 
documentation of the interface changes I have made.

(Note that I have only included the Fibonacci heap here. Whilst I 
have changed the interface on the other heaps to match, they are 
currently crashing on large data sets, and so I won't submit them 
until I have more experience with them).

In my opinion, modifiable priority queues are an essential data 
structure, and so if the members of this list, and in particular 
Dietmar Kühl, are happy with the interface changes I have made, then 
I would hope that these classes could be moved from beta status and 
added to the main library.

,Brian Parker