[Python-ideas] Heap data type, the revival

[Nick Timkovich]

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
(https://mail.python.org/pipermail/python-ideas/2009-April/004173.html),
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)

Open Questions
* 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?

Cheers,
Nick