Python包含了用于min-堆的heapq模块,但我需要一个max堆。在Python中我应该使用什么来实现最大堆?
当前回答
最简单的方法 就是把每个元素都转换成负数,问题就解决了。
import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)
输出如下所示:
[-20, -1, -10]
其他回答
最好的方法:
from heapq import *
h = [5, 7, 9, 1, 3]
h_neg = [-i for i in h]
heapify(h_neg) # heapify
heappush(h_neg, -2) # push
print(-heappop(h_neg)) # pop
# 9
我实现了一个最大堆版本的heapq,并将它提交给PyPI。(对heapq模块CPython代码的改动很小。)
https://pypi.python.org/pypi/heapq_max/
https://github.com/he-zhe/heapq_max
安装
pip install heapq_max
使用
dr:与heapq模块相同,只是所有函数都增加了' _max '。
heap_max = [] # creates an empty heap
heappush_max(heap_max, item) # pushes a new item on the heap
item = heappop_max(heap_max) # pops the largest item from the heap
item = heap_max[0] # largest item on the heap without popping it
heapify_max(x) # transforms list into a heap, in-place, in linear time
item = heapreplace_max(heap_max, item) # pops and returns largest item, and
# adds new item; the heap size is unchanged
你可以使用
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
这是一个基于heapq的简单MaxHeap实现。虽然它只适用于数值。
import heapq
from typing import List
class MaxHeap:
def __init__(self):
self.data = []
def top(self):
return -self.data[0]
def push(self, val):
heapq.heappush(self.data, -val)
def pop(self):
return -heapq.heappop(self.data)
用法:
max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top()) # 5
heapq模块拥有实现maxheap所需的一切。 它只做max-heap的堆推功能。 我已在下面示范如何克服这一点
在heapq模块中添加这个函数:
def _heappush_max(heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
_siftdown_max(heap, 0, len(heap)-1)
最后加上这句话:
try:
from _heapq import _heappush_max
except ImportError:
pass
瞧!这是完成了。
PS -转到heapq函数。首先在编辑器中写入“import heapq”,然后右键单击“heapq”并选择转到定义。
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用pip3安装包时,“Python中的ssl模块不可用”
- 无法切换Python与pyenv
- Python if not == vs if !=
- 如何从scikit-learn决策树中提取决策规则?
- 为什么在Mac OS X v10.9 (Mavericks)的终端中apt-get功能不起作用?
- 将旋转的xtick标签与各自的xtick对齐
- 为什么元组可以包含可变项?
- 如何合并字典的字典?
- 如何创建类属性?
- 不区分大小写的“in”
- 在Python中获取迭代器中的元素个数
- 解析日期字符串并更改格式
- 使用try和。Python中的if
- 如何在Python中获得所有直接子目录