我在Python中使用什么来实现最大堆？

Question

Python中包含heapq模块用于min-heaps，但我需要一个max-heap。在Python中应该使用什么来实现max-heap？

- Douglas Mayle

Answer 1

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

- Daniel Stutzbach

---

这也是标准解决方案。 - Andrew McGregor

唉，总感觉很笨拙。我很惊讶 heapq 没有提供反向排序的功能。 - shabbychef

哇，我很吃惊 heapq 没有提供这个功能，而且也没有好的替代方法。 - ire_and_curses

如果您有一些无法轻松映射到int / float的内容，您可以通过将它们包装在一个具有反向__lt__运算符的类中来反转排序顺序。 - Daniel Stutzbach

同样的建议适用：无论最初是正数还是负数，都应该反转值（即改变符号）。 - Dennis

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

- Lijo Joseph

---

似乎有一些未记录的最大堆函数："_heapify_max"、"_heappushpop_max"、"_siftdown_max"和"_siftup_max"。 - Ziyuan

哇，我很惊讶 heapq 中居然有这样的内置解决方案。但是官方文档中完全没有提到这一点，这真是太不合理了！简直令人发指！ - RayLuo

任何一种弹出/压入函数都会破坏最大堆结构，因此这种方法不可行。 - Siddhartha

不要使用它。正如LinMa和Siddhartha所注意到的，push/pop会破坏顺序。 - Alex Fedulov

以下划线开头的方法是 私有的，可能会被 随时删除。请不要使用它们。 - user4815162342

Answer 3

解决方法是在将值存储到堆中时对其取反，或者倒转对象比较，如下所示：

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"

- Isaac Turner

---

不错。我已经添加了一个可选的list参数到__init__，如果有这个参数，我会调用heapq.heapify方法，并且还增加了一个heapreplace方法。 - Booboo

很惊讶没有人发现这个错别字：MaxHeapInt --> MaxHeapObj。除此之外，这确实是一个非常干净的解决方案。 - Chiraz BenAbdelkader

有趣的是，鲁迅·宝对这个问题的回答非常相似：https://dev59.com/82ox5IYBdhLWcg3w8ItJ - Chiraz BenAbdelkader

这行代码必要吗？def eq(self, other): return self.val == other.val。我认为即使没有它也可以工作。 - apadana

@apadana 是的，拥有它是很好的 - 是否需要取决于 heapify 实现以及您想要对堆执行什么操作。我们只需要定义 __lt__ 和 __eq__ 来方便所有 MaxHeapObj 对象之间的比较（<、<=、==、>、>=），这在搜索堆时可能是必需的。 - Isaac Turner

@ChirazBenAbdelkader Fanchen Bao的链接回答使用了一个带有自定义键对象的元组作为第一个元素，而不是使用自定义对象来包装元素，因此略有不同。元组方法允许传递一个lambda表达式，这很酷。 - Isaac Turner

Answer 4

最简单和理想的解决方案

将数值乘以-1

这样做后，所有最大的数字现在都是最小的，反之亦然。

只需记住，当您弹出一个元素时，要将其乘以-1以获得原始值。

- Sebastian Nielsen

---

很好，但大多数解决方案支持类/其他类型，并不会改变实际数据。开放的问题是，如果将值乘以-1不会改变它们（极其精确的浮点数）。 - Alex Baranowski

@AlexBaranowski，这是事实，但这是维护者的反应：https://bugs.python.org/issue27295 - Flair

维护者有权选择不实现某些功能，但在我看来，这个功能实际上很有用。 - Alex Baranowski

这可能是某些编程环节的好解决方案。否则，在应用程序内更改数据并不那么理想。 - Adarsh Trivedi

Answer 5

最简单的方法是将每个元素转换为负数，这样就可以解决您的问题。

import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)

输出结果将会是：

[-20, -1, -10]

- Than Win Hline

---

如果你有一个零需要推入最大堆中怎么办？抱歉，我卡在这里了。 - mding5692

Answer 6

我实现了一个max-heap版本的heapq，并将其提交到了PyPI。这只是对heapq模块的CPython代码进行了微小的更改。

heapq_max

Heapq_max (GitHub)

安装

pip install heapq_max

使用方法

简而言之：与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]                      # The largest item on the heap without popping it
heapify_max(x)                          # Transforms the list into a heap, in-place, in linear time
item = heapreplace_max(heap_max, item)  # Pops and returns the largest item, and
                                        # adds a new item; the heap size is unchanged

- Zhe He

---

此实现使用了heapq.py的私有函数，请避免使用。 - wim

那些条目上的英文，例如在PyPI上，可能需要改进。例如，所有文章都缺失了，并且它应该是“max-heap”（而不是max Heap或maxHeap）。 - Peter Mortensen

Answer 7

我也需要使用一个最大堆，而且我处理的是整数，所以我只需将我从 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()函数。

- Vikas Prasad

Answer 8

这是一个基于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

- Yuchen

---

简单易懂！ - user3732742

最易理解的代码，无需解释。 - Otieno Rowland

这需要堆元素支持否定，而这并不是一定的。 - wim

Answer 9

最简单的方法：

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

- illuminato

---

如何以及为什么它是最好的方法？是什么让它更好呢？ - Peter Mortensen

你正在使用广为人知的标准库，通过反转你的值。 - Harry Moreno

Answer 10

如果您要插入可比较但不类似于int的键，您可能会覆盖它们上的比较运算符（即 <= 变为 >，> 变为 <=）。否则，您可以在heapq模块中覆盖heapq._siftup函数（归根结底，这都是Python代码）。

- rlotun

---

“这只是 Python 代码而已”: 它取决于你的 Python 版本和安装。例如，我安装的 heapq.py 在 309 行之后有一些代码 (# If available, use C implementation)，它恰好执行了该注释所描述的功能。 - tzot