[boost] Re: Stable Heaps

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 1999-12-03 10:49:05

Hi,

>    Are any of the heaps in your heap library stable, in the sense
> that if two equivalent objects are put on the heap it is guaranteed
> that the first one put on the heap will be the first one retrieved? 

No, none of the heaps in the heaps library is stable. The reason for
this are the performance characteristics: You cannot maintain the
performance of the heaps (eg. amortized constant time extraction of the
maximum element) if you want to have them stable. It is not even
possible to extend them in a way to make them stable: the elements are
not stored in an "order" fashion. Basically all heaps maintain a very
simple property, namely that the largest element is the root of a tree.
The various trees differ in the style they use to keep the tree
balanced but there is no efficient way to find an element in the heap.

> If not, a stable_heap template might be a good addition to your
> library.

Basically the standard C++ library already has a stable heap with the
best [asymptotic] performance which can be achieved in this case: It is
called "multiset". However, since this class has a different interface
than the other heaps, it is probably reasonable to provide a
corresponding adapter which gives the common heap interface to the
"multiset". Any volunteer for this..?
__________________________________________________
Do You Yahoo!?
Thousands of Stores.  Millions of Products.  All in one place.
Yahoo! Shopping: http://shopping.yahoo.com