Re: [boost] [heap] A few questions

Subject: Re: [boost] [heap] A few questions
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-06-10 16:02:25

Andrew Hundt wrote:
>   1) Is it possible to iterate through the heap in order of priority with an
> iterator?

No - but the question raises an interesting issue.

If you want to iterate in-order through an entire heap efficiently, you 
should sort the underlying sequence using std::sort_heap and then 
iterate through the result.  Clearly that's incompatible with providing 
a simple iterator interface.

You might want those iterators so that you can iterate through just a 
small part of the heap.  For example, I have some code that uses 
std::partial_sort to sort just enough of a large std::vector to satisfy 
current requirements; this is used to display a scrollable list of 
search results, where the common case is that the user only looks at 
the first screenful (PSEUDO_CODE):

template <typename T>
class vector_sorted_on_demand {
   std::vector<T> impl;
   size_t n_sorted;
public:
   void push_back(const T& val) {
     impl.push_back(val);
     n_sorted = 0;   // This suits the case where everything is added 
before anything is read.
   }
   T operator[](size_t idx) {
     if (idx >= n_sorted) {
       size_t n_to_sort = n_sorted/2 + 10;  // or whatever
       size_t mid = std::max( idx, std::min(n_sorted + n_to_sort, 
impl.size()) );
       std::partial_sort(impl.begin()+n_sorted, impl.begin()+mid, impl.end());
       n_sorted = mid;
     }
     return impl[idx];
   }
};

I could imagine instead maintaining the unsorted portion as a heap, 
with some complexity trade-offs.

It seems to me that this sort of thing is best done using an explicit 
"underlying container" i.e. std::vector, with algorithms on top of it.  
A heap container with iterators just doesn't seem such a good fit: it 
maintains the heap predicate safely, but I don't always want that.

This makes me wonder whether Tim's proposed alternative heap structures 
should perhaps be decomposed slightly, to expose algorithms in the 
style of std::push|pop_heap.  Without that, I can't use e.g. the b_heap 
in this style of "part heap, part sorted" hybrid container.  Is 
extracting algorithms practical?

Regards,  Phil.