[OT] n-way union

[Frits van Bommel]

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