优先级队列

class MaxPQ:
    def __init__(self):
        self.key = [0]
        self.len = 0

    def empty(self):
        return self.len == 0

    def insert(self, k):
        self.key.append(k)
        self.len += 1
        self.swim(self.len)

    def del_max(self):
        m = self.key[1]
        self.swap(1, self.len)
        del self.key[self.len]
        self.len -= 1
        self.sink(1)
        return m

    def swim(self, k):
        while k > 1 and self.less(int(k / 2), k):
            self.swap(k, int(k / 2))
            k = int(k / 2)

    def sink(self, k):
        while 2 * k <= self.len:
            j = 2 * k
            if j < self.len and self.less(j, j + 1):
                j = j + 1
            if not self.less(k, j):
                break
            self.swap(k, j)
            k = j

    def less(self, i, j):
        return self.key[i] < self.key[j]

    def swap(self, i, j):
        self.key[i], self.key[j] = self.key[j], self.key[i]