Summer reading list

[Chad Netzer]

On Tue, 2003-08-12 at 08:56, Joe Cheng wrote:

> Quoting from the comments:
> 
> """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
> heapify(x)           # transforms list into a heap, in-place, in linear time
> item = heapreplace(heap, item) # pops and returns smallest item, and adds
>                                # new item; the heap size is unchanged"""
> 
> It might just be my Java background creeping in (I'm a Python newbie), but,
> wouldn't it be better if this was OO?
> 
> heap = Heap()
> heap.push(item)
> item = heap.pop()
> item = heap[0]
> heapified = Heap(x)
> item = heap.replace(item)
> 
> Otherwise the user could easily break the heap by doing something dumb to
> the list...

True.  But the flexibility of using the builtin is also nice.  For
example, you can add a bunch of objects to the list, then heapify once,
rather than having to call heap.push() a bunch of times (which may be
slower, because you need to maintain the heap property after you push
each new item.)

I think the idea is that, if you want a real Heap class, you can build
one very easily (see below).  And if you don't need a heap class, you
can gain some benefits from this approach because it is exposing and
operating on lists directly.

This probably comes under "practicality beats purity".  (See 'The Zen of
Python', or type "import this" into your Python interpreter)

Quick heap class (any error corrections are appreciated):
---------------------------------------------------------

import heapq

class Heap:
    def __init__( self, heap=[] ):
        heapq.heapify( heap )
        self._heap = heap

    def __getitem__( self, i ):
        return self._heap[ i ]

    def push( self, item ):
        return heapq.heappush( self._heap, item )

    def pop( self ):
        return heapq.heappop( self._heap )

    def replace( self, item ):
        return heapq.heapreplace( self._heap, item )

if __name__ == '__main__':
    # Tests
    heap = Heap()
    heap.push(3)
    heap.push(2)
    heap.push(1)
    item = heap.pop()

    assert item == 1

    item = heap[0]
    assert item == 2

    item = heap.replace(4)
    assert item == 2
    assert heap[0] == 3
    assert heap[1] == 4



-- 
Chad Netzer