Python包含了用于min-堆的heapq模块,但我需要一个max堆。在Python中我应该使用什么来实现最大堆?
当前回答
我还需要使用max-heap,我处理的是整数,所以我只是包装了我需要的heap中的两个方法,如下所示:
import heapq
def heappush(heap, item):
return heapq.heappush(heap, -item)
def heappop(heap):
return -heapq.heappop(heap)
然后,我只是分别用heappush()和heappop()替换了我的heapq.heappush()和heappop()调用。
其他回答
最简单的方法是反转键的值并使用heapq。例如,将1000.0转换为-1000.0,将5.0转换为-5.0。
最简单最理想的解决方案
将这些值乘以-1
好了。所有最高的数字现在都是最低的,反之亦然。
只要记住,当您弹出一个元素与-1相乘以再次获得原始值时。
如果插入的键具有可比性但不像int型,则可能重写它们上的比较操作符(即<=变成>,>变成<=)。否则,您可以重写heapq。heapq模块中的_siftup(最后都是Python代码)。
我还需要使用max-heap,我处理的是整数,所以我只是包装了我需要的heap中的两个方法,如下所示:
import heapq
def heappush(heap, item):
return heapq.heappush(heap, -item)
def heappop(heap):
return -heapq.heappop(heap)
然后,我只是分别用heappush()和heappop()替换了我的heapq.heappush()和heappop()调用。
你可以使用
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 maxheap
推荐文章
- 如何在Python中进行热编码?
- 如何嵌入HTML到IPython输出?
- 在Python生成器上使用“send”函数的目的是什么?
- 是否可以将已编译的.pyc文件反编译为.py文件?
- Django模型表单对象的自动创建日期
- 在Python中包装长行
- 如何计算两个时间串之间的时间间隔
- 我如何才能找到一个Python函数的参数的数量?
- 您可以使用生成器函数来做什么?
- 将Python诗歌与Docker集成
- 提取和保存视频帧
- 使用请求包时出现SSL InsecurePlatform错误
- 如何检索Pandas数据帧中的列数?
- except:和except的区别:
- 错误:“字典更新序列元素#0的长度为1;2是必需的”