def downheap(self, j):
        """向下堆排序"""
        if self.has_left(j):
            left = self.left(j)
            small = left
            if self.has_right(j):
                right = self.right(j)
                if self.data[right] < self.data[left]:
                    small = right
            if self.data[small] < self.data[j]:
                self.swap(small, j)
                self.downheap(small)

    def __init__(self):
        self.data = []

    def __len__(self):
        return len(self.data)

    def add(self, key, value):
        """添加一个元素，并进行向上堆排序"""
        self.data.append(self.Item(key, value))
        self.upheap(len(self.data) - 1)

    def min(self):
        if self.is_empty():
            raise Empty('Priority queue is empty')
        item = self.data[0]
        return (item.key, item.value)

    def remove_min(self):
        if self.is_empty():
            raise Empty('Priority queue is empty')
        self.swap(0, len(self.data) - 1)
        item = self.data.pop()
        self.downheap(0)
        return (item.key, item.value)

python的heapq模块

Python标准包含了heapq模块，但他并不是一个独立的数据结构，而是提供了一些函数，这些函数吧列表当做堆进行管理,而且元素的优先级就是列表中的元素本身,除此之外它的模型与实现方式与刚才我们自己定义的基本相同

有以下函数：