# [Python-ideas] Heap data type

Facundo Batista facundobatista at gmail.com
Sat Apr 18 14:21:45 CEST 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/

```