MinHeap (or minPQ) in python that allows updates to items already in the heap

minheap.py

class MinHeap:
    """Min Heap
    """
    def __init__(self):
        self.N = 0
        self.vals = []
        self.val2pos = {}
        self.pos2key = {}

    @property
    def size(self):
        return self.N

    def _left_child_pos(self, p):
        """Get index of left child
        """
        return 2 * p + 1

    def _right_child_pos(self, p):
        """Get index of right child
        """
        return 2 * p + 2

    def _parent_pos(self, p):
        """Get Index Of parent
        """
        return (p - 1) // 2

    def _swap(self, p, q):
        """Swap values at two locations
        """
        # Swap position-key mapping
        self.pos2key[p], self.pos2key[q] = self.pos2key[q], self.pos2key[p]

        # Swap the values' positions mapping
        val_p = self.vals[p]
        val_q = self.vals[q]
        self.val2pos[val_p], self.val2pos[val_q] = \
            self.val2pos[val_q], self.val2pos[val_p]

        # Swap the actual values
        self.vals[p], self.vals[q] = self.vals[q], self.vals[p]

    def _bubble_up(self, p):
        """Bubble up
        """
        # Repeat until root or the key is greater than parent key
        while p > 0 and self.pos2key[p] < self.pos2key[self._parent_pos(p)]:
            self._swap(self._parent_pos(p), p)
            p = self._parent_pos(p)

    def _bubble_down(self, p):
        """Bubble Down
        """
        LAST_IDX = self.N - 1

        # Repeat while greater than children
        while True:
            # If left child doesn't exist, then done
            left_pos = self._left_child_pos(p)
            if LAST_IDX < left_pos:
                break

            # If left child exists, but right doesn't, proceed w left child
            left_key = self.pos2key[left_pos]
            right_pos = self._right_child_pos(p)
            if LAST_IDX < right_pos:
                if self.pos2key[p] < left_key:
                    break
                self._swap(p, left_pos)
                break

            # Both left and right children exist
            right_key = self.pos2key[right_pos]
            if self.pos2key[p] < min(left_key, right_key):
                break
            if left_key < right_key:
                self._swap(p, left_pos)
                p = left_pos
            else:
                self._swap(p, right_pos)
                p = right_pos

    def is_empty(self):
        return self.N == 0

    def push(self, key, val):
        self.vals.append(val)
        self.val2pos[val] = self.N
        self.pos2key[self.N] = key
        self._bubble_up(self.N)
        self.N += 1

    def pop(self):
        """Remove top item in heap
        """
        if self.is_empty():
            raise IndexError("Cannot pop from empty heap")
        self.N -= 1
        self._swap(0, self.N)
        self._bubble_down(0)
        k = self.pos2key.pop(self.val2pos.pop(self.vals[self.N]))
        v = self.vals.pop()
        return k, v

    def peek(self):
        """Return value of top of heap w/o popping"""
        return self.vals[0]

    def contains(self, val):
        """Check if heap contains a value
        """
        return val in self.val2pos

    def decrease_key(self, val, key):
        p = self.val2pos[val]
        self.pos2key[p] = key
        self._bubble_up(p)

    def __str__(self):
        sb = ["pos\tkey\tval"]
        for i in range(self.N):
            sb.append(
                '\t'.join(
                    map(str, (i, self.pos2key[i], self.vals[i]))
                )
            )
        return "\n".join(sb)


if __name__ ==  '__main__':
    h = MinHeap()
    h.push(3, 'c')
    h.push(2, 'b')
    print((2, 'b') == h.pop())
    print((3, 'c') == h.pop())

    h.push(4, 'x')
    h.push(3, 'y')
    h.decrease_key('x', 1)
    print((1, 'x') == h.pop())