在Python中如何实现最大堆？

Question

Python有一个叫做heapq的模块，主要是用来处理最小堆的。但是我需要的是最大堆。那我在Python中应该怎么实现最大堆呢？

Answer 1

解决这个问题的方法是在把值存储到堆里时，把它们取反，或者像这样反转你的对象比较：

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, MaxHeapObj(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"

Answer 2

你可以使用

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

Answer 3

最简单的方法是把键的值反转一下，然后使用heapq这个工具。比如，把1000.0变成-1000.0，把5.0变成-5.0。