# 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


class MinPQ(object):
    pq = None
    N = 0

    def __init__(self, capacity=None):
        if capacity is None:
            capacity = 10
        self.pq = [0] * capacity

    def enqueue(self, key):
        self.N += 1
        if self.N == len(self.pq):
            self.resize(len(self.pq) * 2)

        self.pq[self.N] = key
        self.swim(self.N)

    def swim(self, k):
        while k > 1:
            parent = k // 2
            if less(self.pq[k], 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



class MinPQ(object):
    pq = None
    N = 0

    def __init__(self, capacity=None):
        if capacity is None:
            capacity = 10
        self.pq = [0] * capacity

    def enqueue(self, key):
        self.N += 1
        if self.N == len(self.pq):
            self.resize(len(self.pq) * 2)

        self.pq[self.N] = key
        self.swim(self.N)

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

                exchange(self.pq, k, parent)