[OT] n-way union

[Andrei Alexandrescu]

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