Re: [boost] [gsoc] heap review

Subject: Re: [boost] [gsoc] heap review
From: Cliff Green (cliffg_at_[hidden])
Date: 2011-05-11 13:18:48

>From the docs on stable priority queue:

"If a priority queue is configured to be stable, an integer timestamp is 
associated with each node, specifying the time ..."

I was one of the people discussing priority queue use cases, probably a year 
ago, and specifically was wanting a stable priority queue. I also said that 
adding a time stamp or counter to each entry was a naïve approach (and one 
that I had done myself in about an hour, adapting a std::priority_queue). I 
asked for a true, "native" implementation of a stable priority queue, 
because adding a time stamp to each entry has a couple of drawbacks:

1) It adds storage to each element - while for many (most?) applications 
this extra storage is negligible, in some cases it is not negligible 
(embedded systems with large queues)
2) It can fail - if a true time stamp is used, what happens when times are 
adjusted? If a counter is used, what happens when the counter overflows? 
While the failures are edge cases, there's no need to have any failures.

I can dig out the e-mail, if more details of the discussion are needed. I'm 
a bit perplexed that either this discussion was completely missed, or 
somehow "read but misremembered, with the opposite of the desired result".

There must be heap data structures for priority queues that preserve order 
(with no extra memory) at the cost of being slightly slower (but still with 
the same big-O complexity). This is what I expect of a Boost library - 
finding and implementing the best, not something naïve and easily thrown 
together.

So this gives me very little confidence for a robust, world-class 
implementation of heap structures.

Please read this as encouragement to do the hard work, not just the minimum 
necessary for a review, at least for the case mentioned in this e-mail.

Cliff