Frits van Bommel wrote:
Andrei Alexandrescu wrote:
Jason House wrote:
This conversation made me realize a simple optimization (forgive me
if it's what Don was implying)
Instead of storing m ranges in a heap, store only m-1 ranges. The
range that would be the min if the heap is kept separate. Each pop
operation will compare the new front with the min heap element. This
allows avoiding the re-heaping when the next element comes from the
same range. If s is the number of times the source range must switch,
then the performance is O( s*log(m) + n - s). The initial heaping is
O(m*log(m)), but that's never worse than O(s*log(m)). Technically,
the re-heaping steps are log(m-1), but that isn't important with big
O.
Cool! That can actually be implemented as a micro-optimization with
the classic heap: right after you extract from the top (arr[0]), you
look at its children (which are arr[1] and arr[2]). If both front()'s
are still no less than yours, everything stays as it was and you're
home free.
I'll implement this, thanks.
If you keep it separate, you only need one comparison to determine the
current range still contains the minimum element.
Just saying :).
Good point, and also I don't need to worry about adding new heap primitives.
Andrei
