# 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

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

    def del_max(self):
        if self.is_empty():
            return None

        key = self.pq[1]
        exchange(self.pq, 1, self.N)
        self.N -= 1
        if self.N == len(self.pq) // 4:
            self.resize(len(self.pq) // 2)

        self.sink(self.pq, 1, self.N)
        return key

    @staticmethod
    def sink(tmp, k, n):

        while k * 2 <= n:
            child = k * 2
            if child < n and greater(tmp[child + 1], tmp[child]):
                child = child + 1

# 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


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

    def del_max(self):
        if self.is_empty():
            return None

        key = self.pq[1]
        exchange(self.pq, 1, self.N)
        self.N -= 1
        if self.N == len(self.pq) // 4:
            self.resize(len(self.pq) // 2)

        self.sink(self.pq, 1, self.N)
        return key

    @staticmethod
    def sink(tmp, k, n):

        while k * 2 <= n:
            child = k * 2
            if child < n and greater(tmp[child + 1], tmp[child]):
                child = child + 1

            if greater(tmp[child], tmp[k]):