minheap.py

class Minheap(object):
    def __init__(self, array):
        self._array = [None] + array
        self.build_heap()
    def parent_of(self, i):
        return i//2
    def children_of(self, i):
        return 2*i, (2*i)+1
    def build_heap(self):
        for i in xrange(len(self._array)//2, -1, -1):
            self.min_heapify(i)

    def min_heapify(self, i):
        left, right = self.children_of(i)
        min_child_i = left
        if left < len(self._array):
            if right < len(self._array):
                if self._array[left] > self._array[right]:
                    min_child_i = right
            if self._array[i] > self._array[min_child_i]:
                self._array[i], self._array[min_child_i] = \
                    self._array[min_child_i], self._array[i]
                self.min_heapify(min_child_i)
    def pop(self):
        min_val = self._array[1]
        self._array[1] = self._array[-1]
        self.min_heapify(1)
        del self._array[-1]
        return min_val