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


当前回答

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

其他回答

最简单最理想的解决方案

将这些值乘以-1

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

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

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

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

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]

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

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