Skip to content

Instantly share code, notes, and snippets.

@octavifs
Created June 14, 2013 01:54
Show Gist options
  • Save octavifs/5778896 to your computer and use it in GitHub Desktop.
Save octavifs/5778896 to your computer and use it in GitHub Desktop.
Heap class that implements (almost) all the heapq standard python interface. Added some doctests and magic methods for convenience.
import heapq
class Heap(object):
"""
Heap class implementing the heapq interface + some magic methods.
Unit Tests:
>>> h = Heap([1,5,78,2,5,78])
>>> h
Heap([1, 2, 78, 5, 5, 78])
>>> h.pushpop(0)
0
>>> h.nlargest(6)
[78, 78, 5, 5, 2, 1]
>>> h.nsmallest(6)
[1, 2, 5, 5, 78, 78]
>>> h.nlargest(6, lambda x: -x)
[1, 2, 5, 5, 78, 78]
>>> [x for x in h]
[1, 2, 78, 5, 5, 78]
>>> len(h)
6
"""
def __init__(self, container=None, key=None):
if not container:
self._heap = []
else:
self._heap = list(container)
heapq.heapify(self._heap)
self._key = key
def push(self, item):
heapq.heappush(self._heap, item)
def pop(self):
return heapq.heappop(self._heap)
def pushpop(self, item):
return heapq.heappushpop(self._heap, item)
def nlargest(self, n, key=None):
if not key:
key = self._key
return heapq.nlargest(n, self._heap, key)
def nsmallest(self, n, key=None):
if not key:
key = self._key
return heapq.nsmallest(n, self._heap, key)
def __repr__(self):
return "Heap({0})".format(self._heap.__repr__())
def __len__(self):
return len(self._heap)
def __iter__(self):
return iter(self._heap)
if __name__ == '__main__':
import doctest
doctest.testmod()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment