[Python-Dev] Re: heaps

[Zooko]

>From heapq.py:

"""
Usage:

heap = []            # creates an empty heap
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
item = heap[0]       # smallest item on the heap without popping it
...
[It is] possible to view the heap as a regular Python list
without surprises: heap[0] is the smallest item, and heap.sort()
maintains the heap invariant!
"""

Shouldn't heapq be a subclass of list?

Then it would read:

"""
heap = heapq()    # creates an empty heap
heap.push(item)   # pushes a new item on the heap
item = heap.pop() # pops the smallest item from the heap
item = heap[0]    # smallest item on the heap without popping it
"""

In addition to nicer syntax, this would give you the option to forbid 
invariant-breaking alterations.  Although you could also choose to allow 
invariant-breaking alterations, just as the current heapq does.

One thing I don't know how to implement is:

# This changes mylist itself into a heapq -- it doesn't make a copy of mylist!
makeheapq(mylist)

Perhaps this is a limitation of the current object model?  Or is there a way to 
change an object's type at runtime.

Regards,

Zooko

http://zooko.com/