python是否具有内置的min-heap数据结构?

问题描述

python在2.7.3中是否具有内置的min-heap数据结构?

Does python have a built in min-heap data structure in 2.7.3?

我不想导入代码.

我想要类似的东西

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

这可能吗?

推荐答案

就像每个人都说的那样，是heapq-但是，正如没有人提到的那样，它不支持！因此，您需要退回到key=在支持的任何位置内部使用的旧的DSU(装饰-排序-取消装饰)习惯用法(不在heapq中的ala除外，除了功能nlargest和nsmallest除外).确实与模块的其余部分有很大关系.

Like everybody says, heapq is it -- but, as nobody's mentioned yet, it doesn't support a key=! So you need to fall back to the good old DSU (decorate-sort-undecorate) idiom that key= uses internally wherever it's supported (alas not in heapq, except for the functions nlargest and nsmallest that don't really have much to do with the rest of the module).

因此，您可以包装heapq功能，并添加一个密钥，例如在您自己的类中:

So you can wrap heapq functionality, with the addition of a key, e.g in a class of your own:

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 区分pushpop和replace(以及标准库模块heapq提供的其他辅助功能).

See https://docs.python.org/2/library/heapq.html for the distinction between pushpop and replace (and the other auxiliary functions supplied by standard library module heapq).

这篇关于python是否具有内置的min-heap数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！