python是否有内置的最小堆数据结构？

Question

python是否在2.7.3中有内置的最小堆数据结构？

我不想导入代码.

我想要类似的东西

myheap = minheap(key=lambda x: x[1])
myheap.add(obj)
o = myheap.pop()

这可能吗？

Answer 1

就像每个人都说的那样heapq- 但是,正如没人提到的那样,它不支持key=!所以你需要回到好的旧DSU(decorate-sort-undecorate)习语,key=它在内部使用的任何地方都可以使用(唉不在heapq,除了函数,nlargest并且nsmallest与模块的其余部分没有多大关系) ).

所以你可以heapq通过添加一个键来包装功能,例如在你自己的类中:

import heapq

class MyHeap(object):
    def __init__(self, key, data=())
        self.key = key
        self.heap = [(self.key(d), d) for d in data]
        heapq.heapify(self.heap)

    def push(self, item):
        decorated = self.key(item), item
        heapq.heappush(self.heap, decorated)

    def pop(self):
        decorated = heapq.heappop(self.heap)
        return decorated[1]

    def pushpop(self, item):
        decorated = self.key(item), item
        dd = heapq.heappushpop(self.heap, decorated)
        return dd[1]

    def replace(self, item):
        decorated = self.key(item), item
        dd = heapq.heapreplace(self.heap, decorated)
        return dd[1]

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

有关和(以及标准库模块提供的其他辅助功能)之间的区别,请参阅https://docs.python.org/2/library/heapq.html.pushpopreplaceheapq