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


当前回答

如果插入的键具有可比性但不像int型,则可能重写它们上的比较操作符(即<=变成>,>变成<=)。否则,您可以重写heapq。heapq模块中的_siftup(最后都是Python代码)。

其他回答

如果你想用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]

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

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”并选择转到定义。

我创建了一个堆包装器,它将值颠倒以创建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

允许您选择任意数量的最大或最小的项目

import heapq
heap = [23, 7, -4, 18, 23, 42, 37, 2, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapq.heapify(heap)
print(heapq.nlargest(3, heap))  # [42, 42, 37]
print(heapq.nsmallest(3, heap)) # [-4, -4, 2]