efficient idiomatic queue?

[David Eppstein]

In article <mailman.1011127103.4451.python-list at python.org>,
 James_Althoff at i2.com wrote:

> Here's an approach using generators that gets rid of some of the
> "try:except StopIteration" clutter.

Ok, but your merge routine gets rid of a key advantage of using generators: 
it returns a list, rather than yielding the items one at a time, so the 
total time is always Theta(n log n), while for the version I posted (and 
the cleaner ADT-ized version someone else posted later) the merges all 
happen in parallel as items are requested, and the time to pull off the 
first k items from a sorted list of n items is O(n + k log n).
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/