首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >在Python中,我应该使用什么来实现max-heap?

在Python中,我应该使用什么来实现max-heap?
EN

Stack Overflow用户
提问于 2010-03-23 23:58:03
回答 14查看 187.7K关注 0票数 318

Python包含用于min-heaps的heapq模块,但我需要一个max heap。在Python中,我应该使用什么来实现max-heap?

EN

回答 14

Stack Overflow用户

发布于 2010-03-24 00:05:40

最简单的方法是反转键值并使用heapq。例如,将1000.0转换为-1000.0,将5.0转换为-5.0。

票数 343
EN

Stack Overflow用户

发布于 2014-05-14 00:10:52

您可以使用

代码语言:javascript
复制
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!!

如果要弹出元素,请使用:

代码语言:javascript
复制
heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
票数 301
EN

Stack Overflow用户

发布于 2016-11-07 07:32:47

解决方案是当您将值存储在堆中时将其取反,或者像这样反转您的对象比较:

代码语言:javascript
复制
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示例:

代码语言:javascript
复制
maxh = []
heapq.heappush(maxh, MaxHeapObj(x))
x = maxh[0].val  # fetch max value
x = heapq.heappop(maxh).val  # pop max value

但是您必须记住包装和解包您的值,这需要知道您正在处理的是最小堆还是最大堆。

MinHeap,MaxHeap类

添加类

对象可以简化您的代码:

代码语言:javascript
复制
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

示例用法:

代码语言:javascript
复制
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"
票数 118
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2501457

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档