[Python-ideas] priorityqueue, sortedlist in collections?

Adam Olsen rhamph at gmail.com
Fri Mar 2 01:37:37 CET 2007

On 3/1/07, Jason Orendorff <jason.orendorff at gmail.com> wrote:
> I wonder if anyone else finds the heapq and bisect APIs a little dated.
> It seems like these things could be offered in a more intuitive and
> featureful way by making them classes.  They could go in the
> collections module:

I agree, at least for heapq.  The algorithm involves enough voodoo
that it's not obvious how to extend it, so it might as well be wrapped
in a class that hides as much as possible.

The same can't be said for bisect though.  All it does is replace del
a[bisect_left(a, x)] with a.remove(x).  A little cleaner, but no more
obvious.  And the cost is still O(n) since it involves moving all the
pointers after x.

>   class priorityqueue:
Should inherit from object if this is going into 2.x.

>       def __init__(self, elements=(), *,
>           cmp=None, key=None, reversed=False)
>       def add(self, element)
>       def pop(self)  --> remove and return the min element
>       def __iter__(self) --> (while self: yield self.pop())
__iter__ shouldn't modify the container.

>       ...
>       ... any other list methods that make sense
>       ... for example, __len__ but not __getitem__
>       ...

Adam Olsen, aka Rhamphoryncus

More information about the Python-ideas mailing list