我在Python中用于最大堆实现的是什么？
Python包含最小堆的heapq模块，但是我需要一个最大堆。 我应该用什么来实现Python中的最大堆实现？
最简单的方法是反转键的值并使用heapq。 例如，将1000.0转换为-1000.0，将5.0转换为-5.0。
您可以使用
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!!
解决的办法是在你将它们存储在堆中时否定你的值，或者像下面这样反转你的对象比较：
import heapq class MaxHeapObj(object): def __init__(self,val): self.val = val def __lt__(self,other): return self.val > other.val def __eq__(self,other): return self.val == other.val def __str__(self): return str(self.val)
最大堆的例子：
maxh = [] heapq.heappush(maxh,MaxHeapInt(x)) x = maxh[0].val # fetch max value x = heapq.heappop(maxh).val # pop max value
但是你必须记得打包和打开你的值，这需要知道你是在处理最小或最大堆。
MinHeap，MaxHeap类
为MinHeap和MaxHeap对象添加类可以简化您的代码：
class MinHeap(object): def __init__(self): self.h = [] def heappush(self,x): heapq.heappush(self.h,x) def heappop(self): return heapq.heappop(self.h) def __getitem__(self,i): return self.h[i] def __len__(self): return len(self.h) class MaxHeap(MinHeap): def heappush(self,x): heapq.heappush(self.h,MaxHeapObj(x)) def heappop(self): return heapq.heappop(self.h).val def __getitem__(self,i): return self.h[i].val
用法示例：
minh = MinHeap() maxh = MaxHeap() # add some values minh.heappush(12) maxh.heappush(12) minh.heappush(4) maxh.heappush(4) # fetch "top" values print(minh[0],maxh[0]) # "4 12" # fetch and remove "top" values print(minh.heappop(),maxh.heappop()) # "4 12"
如果你插入的键比较类似，但不能像int那样，你可能会覆盖它们上的比较运算符（即<=变成>和>变成<=）。 否则，你可以覆盖heapq模块中的heapq._siftup（最后只是Python代码）。
我实现了heapq的最大堆版本，并将其提交给PyPI。 （heapq模块CPython代码非常轻微的变化）
https://pypi.python.org/pypi/heapq_max/
https://github.com/he-zhe/heapq_max
安装
pip install heapq_max
用法
tl; 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
用-1来重复这个值，然后你去。 所有最高的数字现在是最低的，virca也是如此。
只要记住，当你popup一个元素再次使用-1来重复它时，为了再次获得原始值。
允许您select任意数量的最大或最小项目
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]
我已经创build了一个堆封装器来反转这些值来创build一个最大堆，以及一个最小堆的封装类，使库更像OOP。 这是要点。 有三类; 堆（抽象类），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
