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 :).
