[OT] n-way union
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
hehe... "pretty much in line" turns out to be "exactly the same." Oh well.
More information about the Digitalmars-d