[boost] Re: Dynamic Priority Queues

From: Reid Sweatman (reids_at_[hidden])
Date: 1999-06-24 16:57:58

Well, I'd sure rather not have to, but I'd also like to do this in the
framework of the STL, and the heap functionality has preconditions on both
push and pop that the structure be a heap at the time.  Even if I supply a
random-access iterator (possibly the wrong terminology, since a heap isn't
sorted, save by accident), I'd have to either change the semantics of push
and pop to reorder the heap before doing their business, which would be
about as expensive as a rebuild.  Building a heap is O(N), while pushing and
popping are O(logN).  Without thinking much about it, I'd guess reordering a
heap would probably be something like O(NlogN).  Unfortunately, there's no
algorithm supplied to reorder the heap.  I haven't looked into the internals
of the SGI STL heap algorithm, but I'd guess they're using something like a
splay-tree or some other self-balancing tree to maintain the heap property
on pushes and pops.  However, if I modify a lot (potentially *all*) of the
priorities in the heap between pops or pushes, then it seems to me that for
a heap of any useful size it would probably be faster to simply force a
single rebuild before a push or pop.  A splay tree won't rebalance itself
cheaply if it's badly out of balance; again, it would be cheaper to just
rebuild the tree, which is probably what a heap rebuild is really doing
under the skin.

If I'm wrong on this, and I certainly could be, since, as I said, I haven't
had time to look into the code (major deadline pressure), someone please
correct me.  Thanks.

> -----Original Message-----
> From: Andy Glew [mailto:glew_at_[hidden]]
> Sent: Tuesday, June 22, 1999 7:54 PM
> To: Boost
> Subject: [boost] Re: Dynamic Priority Queues
> 
> 
> >reprioritization occurs considerably more often than popping 
> (since the STL
> >priority queue is *supposed* to be heap-based, you'd want to 
> limit heap
> >rebuilds in such a case).
> 
> 
> Surely you wouldn't have full heap rebuilds?
> 
> Just a bubbleup or down - O(log N)?

------------------------------------------------------------------------

eGroups.com home: http://www.egroups.com/group/boost
http://www.egroups.com - Simplifying group communications