[boost] Re: Stable Heaps

From: Andy Glew (glew_at_[hidden])
Date: 1999-12-03 12:02:19

????????

Creating a stable rooted heap with O(1) inspection
of maximum is trivial:

Extend the keys with an insertion count, and use that
in comparisons.

A fixed size insertion counter, of course, overflows after 
a long time - 2^32, or 2^64, or 2^128 insertions.  If that
is not long enough, recompacting the keys is straightforward,
as long as the size of the heap N is much smaller than the
maximum size of the insertion counter C --- O(N log N)
time with O(1) storage. If you amortize that in the cost of
heap maintenance, it still leaves us at O(log N) insert.

I don't know that I would recommend librarizing such a stable
heap transformation.  I think it was just the pendant in me responding.

> >    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
> 
> ------------------------------------------------------------------------
> -- Easily schedule meetings and events using the group calendar!
> -- http://www.egroups.com/cal?listname=boost&m=1
> 
> 
>