Was verwende ich für eine Max-Heap-Implementierung in Python?

226

Python enthält das Heapq-Modul für Min-Heaps, aber ich brauche einen Max-Heap. Was soll ich für eine Max-Heap-Implementierung in Python verwenden?

Douglas Mayle
quelle

Antworten:

241

Am einfachsten ist es, den Wert der Schlüssel zu invertieren und heapq zu verwenden. Verwandeln Sie beispielsweise 1000.0 in -1000.0 und 5.0 in -5.0.

Daniel Stutzbach
quelle
37
Es ist auch die Standardlösung.
Andrew McGregor
43
uggh; total kludge. Ich bin überrascht, heapqbietet keine Umkehrung.
Shabbychef
40
Beeindruckend. Ich bin erstaunt, dass dies nicht von bereitgestellt wird heapqund dass es keine gute Alternative gibt.
ire_and_curses
23
@gatoatigrado: Wenn Sie etwas haben, das nicht einfach auf int/ abgebildet werden kann, können floatSie die Reihenfolge invertieren, indem Sie sie in eine Klasse mit einem invertierten __lt__Operator einschließen .
Daniel Stutzbach
5
@Aerovistae Der gleiche Rat gilt: Invertieren Sie die Werte (dh wechseln Sie das Vorzeichen), unabhängig davon, ob sie zunächst positiv oder negativ sind.
Dennis
233

Sie können verwenden

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!!

Wenn Sie dann Elemente einfügen möchten, verwenden Sie:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
Lijo Joseph
quelle
34
Sieht aus wie es einige undokumentierte Funktionen für max Heap sind: _heapify_max, _heappushpop_max, _siftdown_max, und _siftup_max.
Ziyuang
127
Beeindruckend. Ich bin erstaunt , dass es IST eine solche integrierte Lösung in heapq. Aber dann ist es völlig unvernünftig, dass es im offiziellen Dokument NICHT einmal geringfügig erwähnt wird! WTF!
RayLuo
27
Jede der Pop / Push-Funktionen unterbricht die maximale Heap-Struktur, sodass diese Methode nicht durchführbar ist.
Siddhartha
22
BENUTZE ES NICHT. Wie LinMa und Siddhartha bemerkten, bricht Push / Pop die Reihenfolge.
Alex Fedulov
13
Die Methoden, die mit einem Unterstrich beginnen, sind privat und können ohne vorherige Ankündigung entfernt werden . Verwenden Sie sie nicht.
user4815162342
66

Die Lösung besteht darin, Ihre Werte zu negieren, wenn Sie sie im Heap speichern, oder Ihren Objektvergleich wie folgt umzukehren:

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)

Beispiel eines Max-Heaps:

maxh = []
heapq.heappush(maxh, MaxHeapObj(x))
x = maxh[0].val  # fetch max value
x = heapq.heappop(maxh).val  # pop max value

Sie müssen jedoch daran denken, Ihre Werte zu verpacken und zu entpacken. Dazu müssen Sie wissen, ob es sich um einen Min- oder Max-Heap handelt.

MinHeap-, MaxHeap-Klassen

Das Hinzufügen von Klassen für MinHeapund MaxHeapObjekte kann Ihren Code vereinfachen:

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

Anwendungsbeispiel:

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
quelle
Nett. Ich habe dies genommen und list__init__ einen optionalen Parameter hinzugefügt. In diesem Fall rufe ich auf heapq.heapifyund füge auch eine heapreplaceMethode hinzu .
Booboo
1
Überrascht, dass niemand diesen Tippfehler entdeckt hat: MaxHeapInt -> MaxHeapObj. Ansonsten eine sehr saubere Lösung.
Chiraz BenAbdelkader
@ChirazBenAbdelkader behoben, danke.
Isaac Turner
39

Die einfachste und ideale Lösung

Multiplizieren Sie die Werte mit -1

Los geht's. Alle höchsten Zahlen sind jetzt die niedrigsten und umgekehrt.

Denken Sie daran, wenn Sie ein Element platzen lassen, um es mit -1 zu multiplizieren, um den ursprünglichen Wert wieder zu erhalten.

Sebastian Nielsen
quelle
Großartig, aber die meisten Lösungen unterstützen die Klassen / anderen Typen und ändern die tatsächlichen Daten nicht. Die offene Frage ist, ob das Multiplizieren des Werts mit -1 diese nicht ändert (extrem präzises Float).
Alex Baranowski
1
@ AlexBaranowski. Das stimmt, aber das war die Antwort des Betreuers: bugs.python.org/issue27295
Flair
Nun, Betreuer haben das Recht, einige Funktionen nicht zu implementieren, aber diese eine IMO ist tatsächlich nützlich.
Alex Baranowski
7

Ich habe eine Max-Heap-Version von Heapq implementiert und an PyPI gesendet. (Sehr geringfügige Änderung des CPython-Codes des Heapq-Moduls.)

https://pypi.python.org/pypi/heapq_max/

https://github.com/he-zhe/heapq_max

Installation

pip install heapq_max

Verwendung

tl; dr: Entspricht dem Heapq-Modul, außer dass allen Funktionen '_max' hinzugefügt wird.

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
Zhe He
quelle
4

Wenn Sie Schlüssel einfügen, die vergleichbar, aber nicht int-ähnlich sind, können Sie möglicherweise die Vergleichsoperatoren überschreiben (dh <= werden> und> werden <=). Andernfalls können Sie heapq._siftup im heapq-Modul überschreiben (am Ende ist alles nur Python-Code).

rlotun
quelle
9
"Es ist alles nur Python-Code": Dies hängt von Ihrer Python-Version und -Installation ab. Zum Beispiel hat meine installierte heapq.py nach Zeile 309 ( # If available, use C implementation) einen Code , der genau das tut, was der Kommentar beschreibt.
Zot
3

Sie können eine beliebige Anzahl der größten oder kleinsten Elemente auswählen

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]
jasonleonhard
quelle
3
Eine Erklärung wäre angebracht.
Peter Mortensen
Mein Titel ist meine Erklärung
Jasonleonhard
1
Meine Antwort ist länger als die Frage. Welche Erklärung möchten Sie hinzufügen?
Jasonleonhard
wikipedia.org/wiki/Min-max_heap und docs.python.org/3.0/library/heapq.html könnten ebenfalls hilfreich sein.
Jasonleonhard
2
Dies liefert das richtige Ergebnis, verwendet jedoch keinen Heap, um es effizient zu machen. Das Dokument gibt an, dass die Liste jedes Mal am größten und am kleinsten sortiert wird.
RossFabricant
3

Das Erweitern der int-Klasse und das Überschreiben von __lt__ ist eine der Möglichkeiten.

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()
Gaurav
quelle
Es ist möglich, aber ich habe das Gefühl, es würde die Dinge sehr verlangsamen und viel zusätzlichen Speicher verbrauchen. MyInt kann auch außerhalb der Heap-Struktur nicht wirklich verwendet werden. Aber danke, dass Sie ein Beispiel geschrieben haben, es ist interessant zu sehen.
Leo Ufimtsev
Hah! Einen Tag nach meinem Kommentar stieß ich auf die Situation, in der ich ein benutzerdefiniertes Objekt in einen Heap einfügen musste und einen maximalen Heap benötigte. Ich habe diesen Beitrag tatsächlich neu gegoogelt und Ihre Antwort gefunden und meine Lösung daraus abgeleitet. (Benutzerdefiniertes Objekt ist ein Punkt mit x-, y-Koordinate und lt überschreibt den Vergleichsabstand vom Zentrum). Vielen Dank für die Veröffentlichung, ich habe gestimmt!
Leo Ufimtsev
1

Ich habe einen Heap-Wrapper erstellt, der die Werte invertiert, um einen Max-Heap zu erstellen, sowie eine Wrapper-Klasse für einen Min-Heap, um die Bibliothek OOP-ähnlicher zu machen. Hier ist das Wesentliche. Es gibt drei Klassen; Heap (abstrakte Klasse), HeapMin und HeapMax.

Methoden:

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
noɥʇʎԀʎzɐɹƆ
quelle
0

Wenn Sie das größte K-Element mit max heap erhalten möchten, können Sie den folgenden Trick ausführen:

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]
RowanX
quelle
1
Leider ist die zeitliche Komplexität hierfür O (MlogM), wobei M = len (nums) ist, was den Zweck von heapq zunichte macht. Siehe die Implementierung und Kommentare nlargesthier -> github.com/python/cpython/blob/…
Arthur S
1
Vielen Dank für Ihren informativen Kommentar. Überprüfen Sie unbedingt den angehängten Link.
RowanX
0

Nach Isaac Turners hervorragender Antwort möchte ich ein Beispiel basierend auf K Closest Points to the Origin unter Verwendung von Max Heap setzen.

from math import sqrt
import heapq


class MaxHeapObj(object):
    def __init__(self, val):
        self.val = val.distance
        self.coordinates = val.coordinates

    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)


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 peek(self):
        return heapq.nsmallest(1, self.h)[0].val

    def __getitem__(self, i):
        return self.h[i].val


class Point():
    def __init__(self, x, y):
        self.distance = round(sqrt(x**2 + y**2), 3)
        self.coordinates = (x, y)


def find_k_closest(points, k):
    res = [Point(x, y) for (x, y) in points]
    maxh = MaxHeap()

    for i in range(k):
        maxh.heappush(res[i])

    for p in res[k:]:
        if p.distance < maxh.peek():
            maxh.heappop()
            maxh.heappush(p)

    res = [str(x.coordinates) for x in maxh.h]
    print(f"{k} closest points from origin : {', '.join(res)}")


points = [(10, 8), (-2, 4), (0, -2), (-1, 0), (3, 5), (-2, 3), (3, 2), (0, 1)]
find_k_closest(points, 3)
Apoorv Patne
quelle
0

Zur Erläuterung von https://stackoverflow.com/a/59311063/1328979 finden Sie hier eine vollständig dokumentierte, kommentierte und getestete Python 3-Implementierung für den allgemeinen Fall.

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

Marc Carré
quelle
0

Dies ist eine einfache MaxHeapImplementierung basierend auf heapq. Es funktioniert jedoch nur mit numerischen Werten.

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)

Verwendung:

max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top())  # 5
Yuchen Zhong
quelle