Python包含了用于min-堆的heapq模块,但我需要一个max堆。在Python中我应该使用什么来实现最大堆?
当前回答
扩展int类并重写__lt__是一种方法。
import queue
class MyInt(int):
def __lt__(self, other):
return self > other
def main():
q = queue.PriorityQueue()
q.put(MyInt(10))
q.put(MyInt(5))
q.put(MyInt(1))
while not q.empty():
print (q.get())
if __name__ == "__main__":
main()
其他回答
最简单最理想的解决方案
将这些值乘以-1
好了。所有最高的数字现在都是最低的,反之亦然。
只要记住,当您弹出一个元素与-1相乘以再次获得原始值时。
最简单的方法 就是把每个元素都转换成负数,问题就解决了。
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
我创建了一个名为heap_class的包,它实现了最大堆,还将各种堆函数包装到一个与列表兼容的环境中。
>>> from heap_class import Heap
>>> h = Heap([3, 1, 9, 20], max=True)
>>> h.pop()
20
>>> h.peek() # same as h[0]
9
>>> h.push(17) # or h.append(17)
>>> h[0] # same as h.peek()
17
>>> h[1] # inefficient, but works
9
从最大堆中获得最小堆。
>>> y = reversed(h)
>>> y.peek()
1
>>> y # repr is inefficient, but correct
Heap([1, 3, 9, 17], max=False)
>>> 9 in y
True
>>> y.raw() # underlying heap structure
[1, 3, 17, 9]
正如其他人所提到的,在max堆中处理字符串和复杂对象在heapq中是相当困难的,因为它们不同 否定的形式。heap_class实现简单:
>>> h = Heap(('aa', 4), ('aa', 5), ('zz', 2), ('zz', 1), max=True)
>>> h.pop()
('zz', 2)
支持自定义键,并与后续的推/追加和弹出一起工作:
>>> vals = [('Adam', 'Smith'), ('Zeta', 'Jones')]
>>> h = Heap(vals, key=lambda name: name[1])
>>> h.peek() # Jones comes before Smith
('Zeta', 'Jones')
>>> h.push(('Aaron', 'Allen'))
>>> h.peek()
('Aaron', 'Allen')
(实现是建立在heapq函数上的,所以它都是用C语言或C语言包装的,除了Python中max heap上的heappush和heapreplace)
扩展int类并重写__lt__是一种方法。
import queue
class MyInt(int):
def __lt__(self, other):
return self > other
def main():
q = queue.PriorityQueue()
q.put(MyInt(10))
q.put(MyInt(5))
q.put(MyInt(1))
while not q.empty():
print (q.get())
if __name__ == "__main__":
main()
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用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中获得所有直接子目录