binary_heap.py

class MinHeap(object):

    def __init__(self):
        self.storage = []

    def add(self, val):
        self.storage.append(val)
        self._percolate_up()

    def get_min(self):
        if not self.storage:
            return None
        if len(self.storage) == 1:
            return self.storage.pop()
        m = self.storage[0]
        self.storage[0] = self.storage.pop()
        self._sift_down()
        return m

    def _swap(self, i, j):
        self.storage[i] += self.storage[j]
        self.storage[j] = self.storage[i] - self.storage[j]
        self.storage[i] = self.storage[i] - self.storage[j]

    def _percolate_up(self):
        if not self.storage:
            return
        i = len(self.storage) - 1
        while i != 0:
            parent = (i - 1) // 2
            if self.storage[parent] > self.storage[i]:
                self._swap(parent, i)
            i = parent

    def _sift_down(self):
        i = 0
        while True:
            left_child = 2 * i + 1
            right_child = 2 * i + 2
            storage_len = len(self.storage) - 1
            if left_child > storage_len:
                return
            smallest = (left_child if right_child > storage_len or
                        self.storage[left_child] <= self.storage[right_child] else right_child)
            if self.storage[i] > self.storage[smallest]:
                self._swap(i, smallest)
            i = smallest