From: Geurt Vos (G.Vos_at_[hidden])
Date: 2001-04-18 07:01:07
> > I will try to get them compiled for at least
> > BC++5.5 and VC++ 6. This is not necessarily
> > integrating stuff into boost. It's merely the
> > first step.
> Some problem with d-heaps can be the use of non-type template arguments
> for "d", ie. the number of children in the tree (a d-heap is a d-nary
> tree which is fully balanced; typically, d == 2 as is eg. the case in
> 'std::priority_queue' but other d's might actually be better).
I'll look into it...
> > I already did some timing tests on Borland,
> > with different implementations for stable
> > priority queues. In the test I only measured
> > the time it takes to push an element. 10
> > elements are pushed. The first 5 are unique,
> > the second 5 are equivalent to the 'middle'
> > item.
> I wouldn't call a total of 10 elements as representative...
I know :)
Anyways, I created a (I hope) more appropriate test. This time
integers only. Pushed onto the queue are 10,000 and 100,000
random integer values. Then 5 equivalent values are pushed,
and the time this takes is measured. It was tested for multiset,
boost::priority_queue and fibonacci_heap.
Comparing multiset to fibonacci_heap, for 10k multiset is slightly
faster, for 100k fibonacci_heap is (f_heap seems quite constant).
In both cases priorty_queue is way faster.
So I'll try to get the d_heap working, and maybe toss up a
stable_priority_queue which wraps priorty_queue.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk