[Python-ideas] Heap data type, the revival
prometheus235 at gmail.com
Sat Oct 15 14:15:18 EDT 2016
I once again had a use for heaps, and after rewrapping the heapq.heap*
methods for the umpteenth time, figured I'd try my hand at freezing
off that wart.
Some research turned up an older thread by Facundo Batista
but it seems like interest petered out. I shoved an initial pass at a
spec, implementation, and tests (robbed from
<cpython>/Lib/test/test_heapq.py mostly) into a repo at
https://github.com/nicktimko/heapo My spec is basically:
1. Provide all existing heapq.heap* functions provided by the heapq
module as methods with identical semantics
2. Provide limited magic methods to the underlying heap structure
a. __len__ to see how big it is, also for boolean'ing
b. __iter__ to allow reading out to something else (doesn't consume elements)
3. Add peek method to show, but not consume, lowest heap value
4. Allow custom comparison/key operation (to be implemented/copy-pasted)
* Should __init__ shallow-copy the list or leave that up to the
caller? Less memory if the heap object just co-opts it, but user might
accidentally reuse the reference and ruin the heap. If we make our own
list then it's easier to just suck in any arbitrary iterable.
* How much should the underlying list be exposed? Is there a use case
for __setitem__, __delitem__?
* Should there be a method to alter the priority of elements while
preserving the heap invariant? Daniel Stutzbach mentioned dynamically
increasing/decreasing priority of some list elements...but I'm
inclined to let that be a later addition.
* Add some iterable method to consume the heap in an ordered fashion?
More information about the Python-ideas