Python 中内置最大堆 API

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

提前致谢， 林

过去我只是简单地使用过分类容器 https://pypi.python.org/pypi/sortedcontainers's 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

但这会使用更多的内存。