Double-Ended Heaps

Scott David Daniels scott.daniels at
Tue Dec 20 01:59:10 CET 2005

Bryan Olson wrote:
> Scott David Daniels wrote:
>> I've just put together a Double-Ended Heap package.
>> Of course I'd love comments.
> I think there's a typo in:
>     Note that any change to the contents of a DeHeap (and
>     therefore a DeHeap2) any re-arrange the indices of a
>     number of entries in the DeHeap.
> A useful Python class will follow Python convention, where
> relevant convention exists. In this case that means optionally
> passing the ordering relation; look at sort() and sorted().
> Adopting the convention will raises another issue: distinct
> objects can compare as equal, so the DeHeap2 operations that
> find items by value will be at least under-defined, and maybe
> even broken. There are several ways to solve the problem, and
> I don't know of Python convention as to which to choose.
OK, I've a new version out there.

deheap.deheap(iterable=(), key=None, sequence=False)

is a factory function making an appropriate instance.
The testing is not all that thorough on the sequence=True
classes (where even pop can use an index), but I suspect it
all works (famous last words).

--Scott David Daniels
scott.daniels at

More information about the Python-list mailing list