RE: [boost] 'stable' priority queue

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.

Geurt