Dou*_*yle 197 python heap recursive-datastructures data-structures
Python包含用于min-sheaps的heapq模块,但我需要一个最大堆.我应该在Python中使用什么来实现max-heap实现？
Dan*_*ach 198
最简单的方法是反转键的值并使用heapq.例如,将1000.0转换为-1000.0,将5.0转换为-5.0.
Lij*_*eph 190
您可以使用
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!!
如果您想要弹出元素,请使用:
heapq.heappop(minheap) # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
Isa*_*ner 50
解决方案是在将它们存储在堆中时否定您的值,或者反转您的对象比较,如下所示:
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对象添加类可以简化代码:
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"
Seb*_*sen 25
将值乘以-1,然后就可以了.现在所有最高的数字都是最低的,反之亦然.
请记住,当您弹出一个元素再次与-1相乘时,为了再次获得原始值.
Vik*_*sad 18
我还需要使用最大堆，并且我正在处理整数，所以我只包装了我需要的两个方法，heap如下所示：
import heapq
def heappush(heap, item):
return heapq.heappush(heap, -item)
def heappop(heap):
return -heapq.heappop(heap)
然后我只是分别用和替换了我的heapq.heappush()和heapq.heappop()电话。heappush()heappop()
Zhe*_* He 11
我实现了 heapq 的最大堆版本并将其提交给 PyPI。（heapq 模块 CPython 代码的细微变化。）
https://pypi.python.org/pypi/heapq_max/
https://github.com/he-zhe/heapq_max
安装
pip install heapq_max
用法
tl;dr：除了向所有函数添加“_max”外，与 heapq 模块相同。
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
Yuc*_*ong 11
这是一个MaxHeap基于heapq. 虽然它只适用于数值。
import heapq
from typing import List
class MaxHeap:
def __init__(self):
self.data = []
def top(self):
return -self.data[0]
def push(self, val):
heapq.heappush(self.data, -val)
def pop(self):
return -heapq.heappop(self.data)
用法：
max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top()) # 5
Tha*_*ine 11
最简单的方法 是将每个元素转换为负数，它会解决您的问题。
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
如果您要插入可比较但不是类似 int 的键，您可能会覆盖它们上的比较运算符（即 <= 变为 > 和 > 变为 <=）。否则，您可以覆盖 heapq 模块中的 heapq._siftup （最后，这只是 Python 代码）。