A simple heap class for dijkstra's algorithm

heap.py

#!/usr/bin/python

import operator

def parent(i):
    return i/2

def left(i):
    return i*2 + 1

def right(i):
    return i*2 + 2

def has_parent(i):
    return i != 0

class Heap(object):
    def __init__(self, lt=operator.lt):
        self.heap = []
        self.keys = {}
        self.lt = lt

    def pop(self):
        m = self.heap[0]
        i = len(self.heap)-1
        self.swap(0, i)
        del self.keys[self.heap[i][0]]
        self.heap.pop()

        if self.heap:
            self.down_heapify(0)
        return m

    def min(self):
        return self.heap[0]

    def insert(self, node, val):
        self.heap.append([node, val])
        i = len(self.heap)-1
        self.keys[node] = i
        self.up_heapify(i)

    def decrease_key(self, node, newval):
        i = self.keys[node]
        self.heap[i][1] = newval
        self.up_heapify(i)

    def has_children(self, i):
        l = len(self.heap)
        return True if left(i) < l or right(i) < l else False

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        self.keys[self.heap[i][0]] = i
        self.keys[self.heap[j][0]] = j

    def min_child(self, i):
        l = left(i)
        r = right(i)
        length = len(self.heap)

        if l < length and r < length:
            return min(l, r, key=lambda x: self.heap[x][1])
        elif l < length:
            return l
        else:
            return r

    def less_than(self, i, j):
        return self.lt(self.heap[i][1], self.heap[j][1])

    def down_heapify(self, i):
        self.keys[self.heap[i][0]] = i
        while self.has_children(i):
            m = self.min_child(i)
            if self.less_than(m, i):
                self.swap(i, m)
                i = m
            else:
                break

    def up_heapify(self, i):
        while has_parent(i):
            p = parent(i)
            if self.less_than(i, p):
                self.swap(i, p)
                i = p
            else:
                break