# Path: pyalgs/algorithms/commons/util.py
# def less(a, b):
#     return cmp(a, b) < 0
# 
# def exchange(a, i, j):
#     tmp = a[j]
#     a[j] = a[i]
#     a[i] = tmp
# 
# def greater(a, b):
#     return cmp(a, b) > 0


from pyalgs.algorithms.commons.util import less, exchange, greater
    keys = None
    pq = None
    qp = None
    N = 0

    def __init__(self, size):
        self.keys = [None] * (size+1)
        self.pq = [0] * (size+1)
        self.qp = [0] * (size+1)

    def insert(self, index, key):
        self.keys[index] = key
        self.N += 1
        self.pq[self.N] = index
        self.qp[index] = self.N

        self.swim(self.N)

    def decrease_key(self, index, key):
        self.keys[index] = key
        k = self.qp[index]
        self.swim(k)

    def contains_index(self, index):
        return self.keys[index] is not None

    def swim(self, k):
        while k > 1:
            parent = k // 2
            if less(self.keys[self.pq[k]], self.keys[self.pq[parent]]):

# Path: pyalgs/algorithms/commons/util.py
# def less(a, b):
#     return cmp(a, b) < 0
# 
# def exchange(a, i, j):
#     tmp = a[j]
#     a[j] = a[i]
#     a[i] = tmp
# 
# def greater(a, b):
#     return cmp(a, b) > 0


# Path: pyalgs/data_structures/commons/priority_queue.py
from pyalgs.algorithms.commons.util import less, exchange, greater

    keys = None
    pq = None
    qp = None
    N = 0

    def __init__(self, size):
        self.keys = [None] * (size+1)
        self.pq = [0] * (size+1)
        self.qp = [0] * (size+1)

    def insert(self, index, key):
        self.keys[index] = key
        self.N += 1
        self.pq[self.N] = index
        self.qp[index] = self.N

        self.swim(self.N)

    def decrease_key(self, index, key):
        self.keys[index] = key
        k = self.qp[index]
        self.swim(k)

    def contains_index(self, index):
        return self.keys[index] is not None

    def swim(self, k):
        while k > 1:
            parent = k // 2
            if less(self.keys[self.pq[k]], self.keys[self.pq[parent]]):

                exchange(self.pq, k, parent)