class MaxHeap:
    """
    最大堆：索引第一位优先级最高
    """

    def __init__(self):
        self.data = []
        self.count = -1

    def add(self, priority, value):
        self.data.append((priority, value))
        self.count += 1
        self.siftup(self.count)  # 向上堆排序

    def extract(self):
        if self.count == -1:
            raise Exception("堆为空！")
        elif self.count == 0:
            self.count -= 1
            return self.data[0]
        else:
            value = self.data[0]
            self.data[0] = self.data[self.count]  # 最右下节点值放到root
            self.count -= 1
            self.data.pop()  # 删除最右下节点
            self.siftdown(0)  # 向下堆排序
            return value

    def siftup(self, index):
        if index != 0:
            parent = int((index - 1) / 2)
            if self.data[index] > self.data[parent]:
                self.data[index], self.data[parent] = self.data[parent], self.data[index]
            self.siftup(parent)

    def siftdown(self, index):
        left = index * 2 + 1
        right = index * 2 + 2
        if left < len(self.data):
            big = left
            if right < len(self.data):
                if self.data[left] < self.data[right]:
                    big = right
            if self.data[index] < self.data[big]:
                self.data[index], self.data[big] = self.data[big], self.data[index]
                self.siftdown(big)


class PriorityQueue:
    def __init__(self):
        self._MaxHeap = MaxHeap()

    def push(self, priority, value):
        self._MaxHeap.add(priority, value)

    def pop(self):
        return self._MaxHeap.extract()


def test_priority_queue():
    pq = PriorityQueue()
    pq.push(10, 'a')
    pq.push(6, 'b')
    pq.push(7, 'c')
    pq.push(3, 'd')
    print(pq.pop())
    print(pq.pop())
    print(pq.pop())
    print(pq.pop())


if __name__ == "__main__":
    test_priority_queue()