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

Question

Python 包含 heapq 模块。 wikipedia.org/wiki/Binary_heap" rel="noreferrer">min-heaps，但我需要一个 最大堆。我应该使用什么来实现 Python 中的最大堆？

Answer 1

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

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

解决方案是在将值存储在堆中时对它们取反，或者反转对象比较，如下所示：

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 4

最简单且理想的解决方案

将值乘以 -1

就可以了。所有最高的数字现在都是最低的，反之亦然。

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

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]

Answer 6

我还需要使用最大堆，而且我正在处理整数，所以我只是从 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() 进行调用。

Answer 7

我实现了 heapq 的 max-heap 版本并将其提交给 PyPI。 （heapq 模块的 CPython 代码有非常细微的变化。）

heapq_max

Heapq_max (GitHub)

安装

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]                      # 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

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

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

Answer 10

如果您要插入可比较但不类似 int 的键，则可能会覆盖它们上的比较运算符（即 <= 变为 > 且 > 变为 <=）。否则，您可以覆盖 heapq 模块中的 heapq._siftup （最终，这只是 Python 代码）。

Answer 11

扩展 int 类并重写 __lt__ 是方法之一。

import queue
class MyInt(int):
    def __lt__(self, other):
        return self > other

def main():
    q = queue.PriorityQueue()
    q.put(MyInt(10))
    q.put(MyInt(5))
    q.put(MyInt(1))
    while not q.empty():
        print (q.get())


if __name__ == "__main__":
    main()

Answer 12

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

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]

Answer 13

我创建了一个堆包装器，它反转值以创建最大堆，以及最小堆的包装器类，以使库更像 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

Answer 14

详细说明 Apoorv Patne 的答案，这里是针对一般情况的完整记录、注释和测试的 Python 3 实现。

from __future__ import annotations  # To allow "MinHeap.push -> MinHeap:"
from typing import Generic, List, Optional, TypeVar
from heapq import heapify, heappop, heappush, heapreplace


T = TypeVar('T')


class MinHeap(Generic[T]):
    '''
    MinHeap provides a nicer API around heapq's functionality.
    As it is a minimum heap, the first element of the heap is always the
    smallest.
    >>> h = MinHeap([3, 1, 4, 2])
    >>> h[0]
    1
    >>> h.peek()
    1
    >>> h.push(5)  # N.B.: the array isn't always fully sorted.
    [1, 2, 4, 3, 5]
    >>> h.pop()
    1
    >>> h.pop()
    2
    >>> h.pop()
    3
    >>> h.push(3).push(2)
    [2, 3, 4, 5]
    >>> h.replace(1)
    2
    >>> h
    [1, 3, 4, 5]
    '''
    def __init__(self, array: Optional[List[T]] = None):
        if array is None:
            array = []
        heapify(array)
        self.h = array
    def push(self, x: T) -> MinHeap:
        heappush(self.h, x)
        return self  # To allow chaining operations.
    def peek(self) -> T:
        return self.h[0]
    def pop(self) -> T:
        return heappop(self.h)
    def replace(self, x: T) -> T:
        return heapreplace(self.h, x)
    def __getitem__(self, i) -> T:
        return self.h[i]
    def __len__(self) -> int:
        return len(self.h)
    def __str__(self) -> str:
        return str(self.h)
    def __repr__(self) -> str:
        return str(self.h)


class Reverse(Generic[T]):
    '''
    Wrap around the provided object, reversing the comparison operators.
    >>> 1 < 2
    True
    >>> Reverse(1) < Reverse(2)
    False
    >>> Reverse(2) < Reverse(1)
    True
    >>> Reverse(1) <= Reverse(2)
    False
    >>> Reverse(2) <= Reverse(1)
    True
    >>> Reverse(2) <= Reverse(2)
    True
    >>> Reverse(1) == Reverse(1)
    True
    >>> Reverse(2) > Reverse(1)
    False
    >>> Reverse(1) > Reverse(2)
    True
    >>> Reverse(2) >= Reverse(1)
    False
    >>> Reverse(1) >= Reverse(2)
    True
    >>> Reverse(1)
    1
    '''
    def __init__(self, x: T) -> None:
        self.x = x
    def __lt__(self, other: Reverse) -> bool:
        return other.x.__lt__(self.x)
    def __le__(self, other: Reverse) -> bool:
        return other.x.__le__(self.x)
    def __eq__(self, other) -> bool:
        return self.x == other.x
    def __ne__(self, other: Reverse) -> bool:
        return other.x.__ne__(self.x)
    def __ge__(self, other: Reverse) -> bool:
        return other.x.__ge__(self.x)
    def __gt__(self, other: Reverse) -> bool:
        return other.x.__gt__(self.x)
    def __str__(self):
        return str(self.x)
    def __repr__(self):
        return str(self.x)


class MaxHeap(MinHeap):
    '''
    MaxHeap provides an implement of a maximum-heap, as heapq does not provide
    it. As it is a maximum heap, the first element of the heap is always the
    largest. It achieves this by wrapping around elements with Reverse,
    which reverses the comparison operations used by heapq.
    >>> h = MaxHeap([3, 1, 4, 2])
    >>> h[0]
    4
    >>> h.peek()
    4
    >>> h.push(5)  # N.B.: the array isn't always fully sorted.
    [5, 4, 3, 1, 2]
    >>> h.pop()
    5
    >>> h.pop()
    4
    >>> h.pop()
    3
    >>> h.pop()
    2
    >>> h.push(3).push(2).push(4)
    [4, 3, 2, 1]
    >>> h.replace(1)
    4
    >>> h
    [3, 1, 2, 1]
    '''
    def __init__(self, array: Optional[List[T]] = None):
        if array is not None:
            array = [Reverse(x) for x in array]  # Wrap with Reverse.
        super().__init__(array)
    def push(self, x: T) -> MaxHeap:
        super().push(Reverse(x))
        return self
    def peek(self) -> T:
        return super().peek().x
    def pop(self) -> T:
        return super().pop().x
    def replace(self, x: T) -> T:
        return super().replace(Reverse(x)).x


if __name__ == '__main__':
    import doctest
    doctest.testmod()

https://gist.github.com/marccarre/577a55850998da02af3d4b7b98152cf4

Answer 15

heapq 模块拥有实现最大堆所需的一切。
它仅执行最大堆的 heappush 功能。
我在下面演示了如何克服这个问题。

在 heapq 模块中添加这个函数：

def _heappush_max(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown_max(heap, 0, len(heap)-1)

最后，添加这个：

try:
    from _heapq import _heappush_max
except ImportError:
    pass

瞧！完成了。

PS - 转到heapq函数。首先在编辑器中写入“import heapq”，然后右键单击“heapq”并选择“转到定义”。

Answer 16

如果您想使用最大堆获得最大的 K 元素，您可以执行以下技巧：

nums= [3,2,1,5,6,4]
k = 2  #k being the kth largest element you want to get
heapq.heapify(nums) 
temp = heapq.nlargest(k, nums)
return temp[-1]

Answer 17

arr = [3, 4, 5, 1, 2, 3, 0, 7, 8, 90, 67, 31, 2, 5, 567]
# max-heap sort will lead the array to ascending order
def maxheap(arr, p):

    for i in range(len(arr)-p):
        if i > 0:
            child = i
            parent = (i + 1)//2 - 1

            while arr[child]> arr[parent] and child != 0:
                arr[child], arr[parent] = arr[parent], arr[child]
                child = parent
                parent = (parent + 1)//2 -1


def heapsort(arr):
    for i in range(len(arr)):
        maxheap(arr, i)
        arr[0], arr[len(arr)-i-1] = arr[len(arr)-i-1], arr[0]

    return arr


print(heapsort(arr))

试试这个。

Answer 18

Python 中有一个内置堆，但以下是您自己构建它的方法。该算法有效，但我不知道效率如何。

class Heap:

    def __init__(self):
        self.heap = []
        self.size = 0

    def add(self, heap):
        self.heap = heap
        self.size = len(self.heap)

    def heappush(self, value):
        self.heap.append(value)
        self.size += 1

    def heapify(self, heap, index=0):

        mid = int(self.size /2)
        """
            If you want to travel great value from the bottom to the top, you need to repeat swapping by the height of the tree.
            I don't know how I can get the height of the tree. That's why I use sezi/2.
            You can find the height by this formula:
            2^(x) = size+1  Why 2^x? Because the tree is growing exponentially
            xln(2) = ln(size+1)
            x = ln(size+1)/ln(2)
        """

        for i in range(mid):
            self.createTee(heap, index)

        return heap

    def createTee(self, heap, shiftindex):

        """
        """
        """

            This 'pos' variable refer to the index of the parent, only parent with children
                    (1)
                (2)      (3)           Here the size of the list is 7/2 = 3
            (4)   (5)  (6)  (7)        The number of parents is 3, but we use {2, 1, 0} in a 'while' loop.
                                       That is why a set 'pos' to -1.

        """
        pos = int(self.size /2) -1
        """
            This if you want to sort this heap list. We should swap the maximum value in the root of the tree with the last
            value in the list and if you want to repeat this until sort all list, you will need to prevent the function from
            change what we already sorted. I should decrease the size of the list. That will heapify on it.

        """

        newsize = self.size - shiftindex
        while pos >= 0:
            left_child = pos * 2 + 1
            right_child = pos * 2 + 2
            # This means that left child is exist
            if left_child < newsize:
                if right_child < newsize:

                    # If the right child exits, we want to check if the left
                    # child > rightchild.
                    #
                    # If the right child doesn't exist, we can check that
                    # we will get error out of range.
                    if heap[pos] < heap[left_child] and heap[left_child]  > heap[right_child]:
                        heap[left_child], heap[pos] = heap[pos], heap[left_child]
                # Here if the right child doesn't exist
                else:
                    if heap[pos] < heap[left_child]:
                        heap[left_child], heap[pos] = heap[pos], heap[left_child]
            # If the right child exists
            if right_child < newsize:
                if heap[pos] < heap[right_child]:
                    heap[right_child], heap[pos] = heap[pos], heap[right_child]
            pos -= 1

        return heap

    def sort(self):
        k = 1
        for i in range(self.size -1, 0, -1):
            """
            Because this is max-heap, we swap root with last element in the list

            """
            self.heap [0], self.heap[i] = self.heap[i], self.heap[0]
            self.heapify(self.heap, k)
            k += 1

        return self.heap


h = Heap()
h.add([5, 7, 0, 8, 9, 10, 20, 30, 50, -1])
h.heappush(-2)
print(" before heapify ")
print(h.heap)
print(" after heapify ")
print(h.heapify(h.heap, 0))
print(" after sort ")
print(h.sort())

输出

heapify 之前

[5, 7, 0, 8, 9, 10, 20, 30, 50, -1, -2]

heapify 之后

[50, 30, 20, 8, 9, 10, 0, 7, 5, - 1, -2]

排序后

[-2, -1, 0, 5, 7, 8, 9, 10, 20, 30, 50]

Answer 19

我创建了一个名为 heap_class 的包，它实现了 max-heaps，并且还将各种堆函数包装到列表兼容的环境中。

>>> from heap_class import Heap
>>> h = Heap([3, 1, 9, 20], max=True)
>>> h.pop()
20

>>> h.peek()  # The same as h[0]
9

>>> h.push(17)  # Or h.append(17)
>>> h[0]  # The same as h.peek()
17

>>> h[1]  # Inefficient, but it works
9

从最大堆中获取最小堆。

>>> y = reversed(h)
>>> y.peek()
1

>>> y  # The representation is inefficient, but correct
Heap([1, 3, 9, 17], max=False)

>>> 9 in y
True

>>> y.raw()  # Underlying heap structure
[1, 3, 17, 9]

正如其他人提到的，由于不同形式的否定，在最大堆中处理字符串和复杂对象在 heapq 中相当困难。使用 heap_class 实现很容易：

>>> h = Heap(('aa', 4), ('aa', 5), ('zz', 2), ('zz', 1), max=True)
>>> h.pop()
('zz', 2)

支持自定义键并可与后续的推送/追加和弹出一起使用：（

>>> vals = [('Adam', 'Smith'), ('Zeta', 'Jones')]
>>> h = Heap(vals, key=lambda name: name[1])
>>> h.peek()  # Jones comes before Smith
('Zeta', 'Jones')

>>> h.push(('Aaron', 'Allen'))
>>> h.peek()
('Aaron', 'Allen')

该实现基于 heapq 函数构建，因此全部用 C 语言或 C 包装器编写，除了 max- 上的 heappush 和 heapreplace 之外Python 中的堆。）

Answer 20

import heapq
customers = []
heapq.heappush(customers, (2, "Harry"))
heapq.heappush(customers, (3, "Charles"))
heapq.heappush(customers, (1, "Riya"))
heapq.heappush(customers, (4, "Stacy"))
while customers:
     print(heapq.heappop(customers)) #for min heap
     # for max heap
     #heapq._heapify_max(customers) 
     #print(heapq._heappop_max(customers))