Double-Ended Heaps

[Scott David Daniels]

Bryan Olson wrote:
> Scott David Daniels wrote:
>> I've just put together a Double-Ended Heap package.
>> Of course I'd love comments.
>>
>>    http://members.dsl-only.net/~daniels/deheap.html
> 
> 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 acm.org