python 关于heapq模块的随笔

heapq模块提供了很多高级功能可以通过help（heapq）查看详细文档：

要点：

1优先级队列让我们可以按照重要程度来处理元素，而不是先进先出

2使用heapq可以应对长列表，因为heap不是复杂的平方级别

3heapq是基于堆的优先级队列，可以处理大量数据

4使用heapq模块，我们必须让元素所在的类型支持自然排序，这可以通过对类套用total_orderding并定义__lt__

语法：

heappush(heap, x) 将x压入堆中

heappop(heap) 从堆中弹出最小的元素

heapify(heap) 让列表具备堆特征

heapreplace(heap, x) 弹出最小的元素，并将x压入堆中

@functools.total_ordering
class A:
    def __init__(self,a,b):
        self.a=a
        self.b=b
    def res(self):
        return (self.a,self.b)
    def __lt__(self, other):
        return self.b > other.b
heap=[]
heappush(heap,A("a","3-1").res())
heappush(heap,A("b","3-2").res())
heappush(heap,A("c","4-1").res())
heappush(heap,A("d","3-3").res())
print(heap)
heappush(heap,A("a","5-1").res())
print(heap)
print(heappop(heap))

python 关于heapq模块的随笔

推荐阅读