[OT] n-way union

[Jason House]

Andrei Alexandrescu Wrote:

> Don wrote:
> > Andrei Alexandrescu wrote:
> >> I think you can't do better. Complexity is O(n) at a minimum because 
> >> you need to go through each element. The heap-based algorithm has O(n 
> >> log m). What you could improve on is the log m factor (m = the number 
> >> of sets).
> > 
> > Depending on what "going through each element" means. Certainly, if you 
> > need to move them, you can't beat O(n) moves, but you can definitely get 
> > O(m*m) < < O(n) comparisons in the best case I described. And that would 
> > also be the number of splicing operations.
> 
> Oh, I see. So yes, comparisons can be reduced. So how exactly do you 
> think that can be done? By binary searching the upper bound of the head 
> to find a long run of identical elements?
> 
> 
> Andrei

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.