[Python-ideas] Heap data type

18 Apr 2009

      Using the module heapq, I found that it's not easy to use. Or, at
least, that it could be straightforward to use.

My main issue is that for correct usage:

- user should provide an external list, that shouldn't use for
anything else to don't break the invariant

- to alter the heap queue, a bunch of functions must be used, passing
always the external list

I think that changing "external list" for "internal attribute", and
"bunch of functions " for "methods", it will leave the module easier
to use, safer, and more object oriented.

So, I basically coded it. What do you think about including this class
in the heap module?

"""
class Heap(object):
    '''Maintains a heapified list, always conserving the invariant.

    Heaps are arrays for which heap[k] <= heap[2*k+1] and
    heap[k] <= heap[2*k+2] for all k, counting elements from zero.
    '''

    def __init__(self, iterable=None):
        '''Initializes the heap from any iterable.

        >>> Heap([1, 2])
        Heap([1, 2])
        >>> Heap([])
        Heap([])
        >>> Heap()
        Heap([])
        >>> Heap((1, 2, 3))
        Heap([1, 2, 3])
        >>> Heap(x**2 for x in range(3))
        Heap([0, 1, 4])
        '''
        if iterable is None:
            self._queue = []
        else:
            self._queue = list(iterable)
            heapq.heapify(self._queue)

    def __repr__(self):
        return "Heap(%s)" % self._queue

    def push(self, item):
        '''Push the item to the heap queue.

        >>> h = Heap()
        >>> h.push(5)
        >>> h.push(4)
        >>> h.push(3)
        >>> h.push(2)
        >>> h.push(1)
        >>> h.push(0)
        >>> h
        Heap([0, 2, 1, 5, 3, 4])
        '''
        heapq.heappush(self._queue, item)

    def pop(self):
        '''Pop one item from the heap queue.

        >>> h = Heap([0, 2, 1, 5, 3, 4])
        >>> h.pop()
        0
        >>> h.pop()
        1
        >>> h.pop()
        2
        >>> h.pop()
        3
        >>> h.pop()
        4
        >>> h.pop()
        5
        >>> h
        Heap([])
        >>> h.pop()
        Traceback (most recent call last):
        ...
        IndexError: index out of range
        '''
        return heapq.heappop(self._queue)

    def pushpop(self, item):
        '''Push the item and pop one from the heap queue.

        Note that this method is more efficient than calling both
        push() and pop() separately.

        >>> h = Heap()
        >>> h.pushpop(7)
        7
        >>> h.push(5)
        >>> h.push(4)
        >>> h.push(3)
        >>> h.pushpop(7)
        3
        >>> h.pushpop(7)
        4
        >>> h
        Heap([5, 7, 7])
        '''
        return heapq.heappushpop(self._queue, item)

    def replace(self, item):
        '''Pop one item and push the received one into the heap queue

        Note that this method is more efficient than calling both
        pop() and push() separately.

        >>> h = Heap()
        >>> h.replace(3)
        Traceback (most recent call last):
        ...
        IndexError: index out of range
        >>> h.push(7)
        >>> h.replace(2)
        7
        >>> h
        Heap([2])
        >>> h.push(3)
        >>> h
        Heap([2, 3])
        >>> h.replace(1)
        2
        >>> h.replace(9)
        1
        >>> h
        Heap([3, 9])
        '''
        return heapq.heapreplace(self._queue, item)
"""

Regards,

-- 
.    Facundo

Blog: http://www.taniquetil.com.ar/plog/
PyAr: http://www.python.org/ar/

[Python-ideas] Heap data type

Facundo Batista