在Python中，我应该使用什么来实现max-heap？
在Python中，我应该使用什么来实现max-heap？
提问于 2010-03-23 23:58:03
Python包含用于min-heaps的heapq模块，但我需要一个max heap。在Python中，我应该使用什么来实现max-heap？
回答 14
Stack Overflow用户
发布于 2010-03-24 00:05:40
最简单的方法是反转键值并使用heapq。例如，将1000.0转换为-1000.0，将5.0转换为-5.0。
Stack Overflow用户
发布于 2014-05-14 00:10:52
您可以使用
import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
heapq.heapify(listForTree) # for a min heap
heapq._heapify_max(listForTree) # for a maxheap!!如果要弹出元素，请使用：
heapq.heappop(minheap) # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheapStack Overflow用户
发布于 2016-11-07 07:32:47
解决方案是当您将值存储在堆中时将其取反，或者像这样反转您的对象比较：
import heapq
class MaxHeapObj(object):
def __init__(self, val): self.val = val
def __lt__(self, other): return self.val > other.val
def __eq__(self, other): return self.val == other.val
def __str__(self): return str(self.val)max-heap示例：
maxh = []
heapq.heappush(maxh, MaxHeapObj(x))
x = maxh[0].val # fetch max value
x = heapq.heappop(maxh).val # pop max value但是您必须记住包装和解包您的值，这需要知道您正在处理的是最小堆还是最大堆。
MinHeap，MaxHeap类
添加类
和
对象可以简化您的代码：
class MinHeap(object):
def __init__(self): self.h = []
def heappush(self, x): heapq.heappush(self.h, x)
def heappop(self): return heapq.heappop(self.h)
def __getitem__(self, i): return self.h[i]
def __len__(self): return len(self.h)
class MaxHeap(MinHeap):
def heappush(self, x): heapq.heappush(self.h, MaxHeapObj(x))
def heappop(self): return heapq.heappop(self.h).val
def __getitem__(self, i): return self.h[i].val示例用法：
minh = MinHeap()
maxh = MaxHeap()
# add some values
minh.heappush(12)
maxh.heappush(12)
minh.heappush(4)
maxh.heappush(4)
# fetch "top" values
print(minh[0], maxh[0]) # "4 12"
# fetch and remove "top" values
print(minh.heappop(), maxh.heappop()) # "4 12"页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2501457
复制相关文章
相似问题
腾讯云开发者
