Python中内置的最大堆API

Question

默认的 heapq 是最小队列实现，我想知道是否有最大队列的选项？谢谢。

我尝试了使用 _heapify_max 实现最大堆，但如何处理动态推入/弹出元素呢？似乎 _heapify_max 只能在初始化时使用。

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

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

提前感谢，Lin

- Lin Ma

---

可能是Python中最大堆的实现方式是什么？的重复问题。 - Lukas Graf

@LukasGraf，我不确定调用函数_heapify_max是否好，因为我看到前缀“_”，这似乎是一个内部函数？ - Lin Ma

是的，这里的情况确实不太令人满意。不过，问题本身几乎是完全重复的。您可能会发现这个答案有所帮助。 - Lukas Graf

@LukasGraf，你发布了一段代码，显示_heapify_max解决方案在我们动态弹出/推入元素的情况下无法使用，期待你的建议。谢谢。 - Lin Ma

_heapify_max可以将您的输入转换为最大堆。但是，heappop和heappush仍然基于最小堆。您可以在此处检查heapq模块的源代码：https://github.com/python/cpython/blob/master/Lib/heapq.py 实际上有一个_heappop_max函数可以导入，应该用于最大堆。没有可用的_heappush_max。但是可以轻松修改heappush函数来编写一个。或者可以在此处查看我的版本：https://github.com/he-zhe/heapq_max/blob/master/heapq_max/heapq_max.py#L47 - Zhe He

Answer 1

过去，我通常使用sortedcontainers的SortedList来完成此操作：

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

虽然它不是一个堆，但它很快，可以直接按要求工作。

如果你确实需要它成为一个堆，你可以创建一个通用的否定类来保存你的项。

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

但这将使用更多的内存。

- U2EF1

---

@LinMa 这就是包装器的作用。如果您知道您的数据是数字，那么您可以通过仅使用“-”来做得更好，例如 def maxheappush(heap, item): heapq.heappush(heap, -item) 和 def maxheappop(heap): return -heapq.heappop(heap)。 - U2EF1

@LinMa 是的，对于 Neg 实例的操作，如 a < b，将调用 __cmp__。如果您想查看它被调用，可以添加一些打印语句。 - U2EF1

使用索引，例如 a[-1]。 - U2EF1

抱歉打扰了这个旧的讨论串，但是针对上面最后一条评论的回复，我认为应该使用 a[0] 来查看最大项（即堆/树的根节点处的项）。 - Thariq Nugrohotomo

对于Python3，实现__lt__就足够了。 - avmohan

Answer 2

最新的cpython源代码中有一个_heappop_max函数，你可能会发现它很有用：

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 逻辑，则应获得所需的输出：

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

输出：

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

- Padraic Cunningham