Python中内置的最大堆API
Python中内置的最大堆API
提问于 2015-10-09 03:19:15
默认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])提前谢谢你，林
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-10-11 15:14:07
在过去，我只是简单地使用sortedcontainers的SortedList来实现这一点，如下所示：
> a = SortedList()
> a.add(3)
> a.add(2)
> a.add(1)
> a.pop()
3它不是一个堆，但它很快，并且直接按要求工作。
如果你绝对需要它是一个堆，你可以创建一个通用的negation类来保存你的项目。
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但这将使用更多的内存。
Stack Overflow用户
发布于 2015-10-12 07:26:11
在最新的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']页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33024215
复制相关文章
相似问题
腾讯云开发者
