内置在Python最大堆API [英] built-in max heap API in Python

问题描述

默认heapq是分队列实现，不知道如果有一个最大队列的选择吗？谢谢你。

Default heapq is min queue implementation and wondering if there is an option for max queue? Thanks.

我试图用_heapify_max为最大堆的解决方案，但如何动态处理推/流行元素？看来_heapify_max只能在初始化时使用。

I tried the solution using _heapify_max for max heap, but how to handle dynamically push/pop element? It seems _heapify_max could only be used during initialization time.

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〕。

Edit, tried _heapify_max seems not working for dynamically push/pop elements. I tried both methods output the same, both output is, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

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])

在此先感谢， 林

Thanks in advance, Lin

推荐答案

在过去，我只是简单地使用 sortedcontainers 的排序列表对于这一点，因为：

In the past I have simply used sortedcontainers's SortedList for this, as:

> a = SortedList()
> a.add(3)
> a.add(2)
> a.add(1)
> a.pop()
3

这不是堆的，但它的快速和直接工作的要求。

It's not a heap, but it's fast and works directly as required.

如果您确实需要它是一个堆，你可以做一个一般的否定类来保存您的项目。

If you absolutely need it to be a heap, you could make a general negation class to hold your items.

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

不过，这将是使用多一点的内存。

But that will be using a little more memory.

这篇关于内置在Python最大堆API的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！