首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >Python中内置的最大堆API

Python中内置的最大堆API
EN

Stack Overflow用户
提问于 2015-10-09 03:19:15
回答 2查看 18.6K关注 0票数 31

默认heapq是最小队列实现,不知道是否有最大队列的选项?谢谢。

我尝试了在最大堆上使用_heapify_max的解决方案,但是如何处理动态推送/弹出元素?_heapify_max似乎只能在初始化期间使用。

代码语言:javascript
复制
import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

if __name__ == "__main__":

    print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

编辑,尝试过的_heapify_max似乎不适用于动态推送/弹出元素。我尝试了两种方法的输出都是一样的,都是0,1,2,3,4,5,6,7,8,9。

代码语言:javascript
复制
def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

def heapsort2(iterable):
    h = []
    heapq._heapify_max(h)
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

if __name__ == "__main__":

    print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
    print heapsort2([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

提前谢谢你,林

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2015-10-11 15:14:07

在过去,我只是简单地使用sortedcontainersSortedList来实现这一点,如下所示:

代码语言:javascript
复制
> a = SortedList()
> a.add(3)
> a.add(2)
> a.add(1)
> a.pop()
3

它不是一个堆,但它很快,并且直接按要求工作。

如果你绝对需要它是一个堆,你可以创建一个通用的negation类来保存你的项目。

代码语言:javascript
复制
class Neg():
    def __init__(self, x):
        self.x = x

    def __cmp__(self, other):
        return -cmp(self.x, other.x)

def maxheappush(heap, item):
    heapq.heappush(heap, Neg(item))

def maxheappop(heap):
    return heapq.heappop(heap).x

但这将使用更多的内存。

票数 30
EN

Stack Overflow用户

发布于 2015-10-12 07:26:11

在最新的cpython源代码中有一个_heappop_max函数,您可能会发现它很有用:

代码语言:javascript
复制
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

如果您使用heapq._siftdown_max更改heappush逻辑,您应该会得到所需的输出:

代码语言:javascript
复制
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()  # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


def heapsort2(iterable):
    h = []
    heapq._heapify_max(h)
    for value in iterable:
        _heappush_max(h, value)
    return [_heappop_max(h) for i in range(len(h))]

输出:

代码语言:javascript
复制
In [14]: heapsort2([1,3,6,2,7,9,0,4,5,8])
Out[14]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

In [15]: heapsort2([7, 8, 9, 6, 4, 2, 3, 5, 1, 0])
Out[15]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

In [16]: heapsort2([19,13,15,17,11,10,14,20,18])
Out[16]: [20, 19, 18, 17, 15, 14, 13, 11, 10]

In [17]: heapsort2(["foo","bar","foobar","baz"])
Out[17]: ['foobar', 'foo', 'baz', 'bar']
票数 7
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/33024215

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档