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


当前回答

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

其他回答

如果你想用max heap得到最大的K元素,你可以做下面的技巧:

nums= [3,2,1,5,6,4]
k = 2  #k being the kth largest element you want to get
heapq.heapify(nums) 
temp = heapq.nlargest(k, nums)
return temp[-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

我创建了一个堆包装器,它将值颠倒以创建max-heap,还为min-heap创建了一个包装器类,以使库更像oop。这是要点。有三个班级;Heap(抽象类),HeapMin和HeapMax。

方法:

isempty() -> bool; obvious
getroot() -> int; returns min/max
push() -> None; equivalent to heapq.heappush
pop() -> int; equivalent to heapq.heappop
view_min()/view_max() -> int; alias for getroot()
pushpop() -> int; equivalent to heapq.pushpop

最简单最理想的解决方案

将这些值乘以-1

好了。所有最高的数字现在都是最低的,反之亦然。

只要记住,当您弹出一个元素与-1相乘以再次获得原始值时。