Python 中内置的最大堆 API
问题描述
默认 heapq 是最小队列实现，想知道是否有最大队列选项?谢谢.
Default heapq is min queue implementation and wondering if there is an option for max queue? Thanks.
我尝试了使用 _heapify_max 作为最大堆的解决方案，但是如何动态处理 push/pop 元素?看来 _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])
提前致谢，林
解决方案
过去我只是简单地使用 sortedcontainers 的 SortedList 为此，如:
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
但这会占用更多内存.
相关文章