Re: [boost] Dietmar Kuehl

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-05-23 16:35:59

On Thu, May 23, 2002 at 08:58:32AM +0200, Dirk Gerrits wrote:
> Well how many of these top functions would you make? I think it would be
> more logical if there were a nth_top function or something.

Unfortunately, you can't support this operation efficiently.

For the second_top, it's easy enough because (assuming some kind of
tree) the second element is always a direct child of the root, so you
only have to take the min of them. Of course, if you don't want to
expose the internals of the queue, you can't leave it to the user.

For nth_top, the same reasoning applies but the best complexity you can
hope for is O(k log k) for kth element in an n-element heap. (Nice
algorithm exercise by the way). For large k, it might be easier to just
pop the elements and reinsert them into the heap in O(k log n) time...
This is simply called heap-sort.

There are relations between all these algorithms and partial_sort, of
course. It's a challenging engineering problem to efficiently reorganize
the heap so that the first elements of [begin(), end()) are actually the
first k elements in sorted order. I would greatly prefer that interface
to the above discussed second_top and nth_top, actually. It'd be neat
(but how useful?) to have a function partial_sort() in the heap interface.

FWIW,
-- 
Hervé