[OT] n-way union

Sean Kelly sean at invisibleduck.org
Sat May 23 12:06:11 PDT 2009

Sean Kelly wrote:
> I have a better idea which is pretty much in line with the heap-based 
> solutions already posted.  Place all the ranges in a min priority queue 
> where the priority of a range is equal to the value of its top element. 
>  Pop the value off the heap at the front of the queue.  If the heap is 
> empty then remove it.  If it contains more elements then fix up the 
> priority queue to restore the invariant (since the priority of the head 
> range may have changed).  The temporary space would just be of size N 
> where N is the number of ranges, and the number of duplicate compares is 
> minimized.

hehe... "pretty much in line" turns out to be "exactly the same."  Oh well.

More information about the Digitalmars-d mailing list