Czego używam do implementacji max-sterty w Pythonie?

Odpowiedzi:

241

Najprostszym sposobem jest odwrócenie wartości kluczy i użycie heapq. Na przykład zmień 1000,0 na -1000,0 i 5,0 na -5,0.

Daniel Stutzbach
źródło
37
To także standardowe rozwiązanie.
Andrew McGregor
43
uggh; całkowita kludge. Jestem zaskoczony, heapqże nie zapewnia odwrotności.
shabbychef
40
Łał. Dziwi mnie, że tego nie zapewnia heapqi że nie ma dobrej alternatywy.
ire_and_curses
23
@gatoatigrado: Jeśli masz coś, co nie daje się łatwo zmapować do int/ float, możesz odwrócić kolejność, zawijając je w klasie odwróconym __lt__operatorem.
Daniel Stutzbach,
5
@Aerovistae obowiązuje ta sama rada: odwróć wartości (tj. Zmień znak) niezależnie od tego, czy na początku będzie dodatnia czy ujemna.
Dennis
233

Możesz użyć

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

Jeśli następnie chcesz wyskoczyć elementy, użyj:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
Lijo Joseph
źródło
34
Wygląda na to, istnieją pewne nieudokumentowane funkcje max sterty: _heapify_max, _heappushpop_max, _siftdown_max, i _siftup_max.
ziyuang
127
Łał. Jestem zdumiony , że JEST taki wbudowany w roztworze heapq. Ale wtedy jest całkowicie nierozsądne , aby NIE było nawet w ogóle wspomniane w oficjalnym dokumencie! WTF!
RayLuo
27
Każda z funkcji pop / push psuje strukturę maksymalnej sterty, więc ta metoda jest niewykonalna.
Siddhartha,
22
NIE UŻYWAJ TEGO. Jak zauważyli LinMa i Siddhartha, push / pop psuje porządek.
Alex Fedulov,
13
Metody zaczynające się od podkreślenia są prywatne i można je usunąć bez uprzedniego powiadomienia . Nie używaj ich.
user4815162342
66

Rozwiązaniem jest zanegowanie wartości podczas przechowywania ich w stercie lub odwrócenie porównania obiektów w następujący sposób:

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)

Przykład maksymalnego stosu:

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

Ale musisz pamiętać, aby zawijać i rozpakowywać swoje wartości, co wymaga wiedzy, czy masz do czynienia ze stertą minimalną lub maksymalną.

Klasy MinHeap, MaxHeap

Dodanie klas MinHeapi MaxHeapobiektów może uprościć kod:

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

Przykładowe użycie:

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
źródło
Miły. Wziąłem to i dodałem opcjonalny listparametr do __init__, w którym to przypadku wywołuję heapq.heapifyi dodałem również heapreplacemetodę.
Booboo
1
Zaskoczony, że nikt nie złapał tej literówki: MaxHeapInt -> MaxHeapObj. W przeciwnym razie rzeczywiście bardzo czyste rozwiązanie.
Chiraz BenAbdelkader
@ChirazBenAbdelkader naprawiono, dziękuję.
Isaac Turner
39

Najłatwiejsze i idealne rozwiązanie

Pomnóż wartości przez -1

Proszę bardzo. Wszystkie najwyższe liczby są teraz najniższe i odwrotnie.

Pamiętaj tylko, że kiedy wstawisz element, pomnóż go przez -1, aby ponownie uzyskać oryginalną wartość.

Sebastian Nielsen
źródło
Świetnie, ale większość rozwiązań obsługuje klasy / inne typy i nie zmienia rzeczywistych danych. Otwarte pytanie dotyczy tego, czy pomnożenie wartości przez -1 nie zmieni ich (niezwykle precyzyjna liczba zmiennoprzecinkowa).
Alex Baranowski,
1
@AlexBaranowski. To prawda, ale taka była odpowiedź opiekuna: bugs.python.org/issue27295
Flair
Cóż, opiekunowie mają prawo nie wdrażać niektórych funkcji, ale ten IMO jest w rzeczywistości przydatny.
Alex Baranowski
7

Zaimplementowałem wersję sterty o maksymalnej wysokości stosu i przesłałem ją do PyPI. (Bardzo niewielka zmiana kodu CPython modułu heapq.)

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

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

Instalacja

pip install heapq_max

Stosowanie

tl; dr: to samo co moduł heapq z wyjątkiem dodania „_max” do wszystkich funkcji.

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
źródło
4

Jeśli wstawiasz klucze, które są porównywalne, ale nie int-like, możesz potencjalnie zastąpić na nich operatory porównania (tj. <= Stać się> i> stać <=). W przeciwnym razie możesz zastąpić heapq._siftup w module heapq (w końcu to wszystko jest tylko kodem Python).

Rlotun
źródło
9
„Wszystko to tylko kod Pythona”: zależy od wersji i instalacji Pythona. Na przykład mój zainstalowany heapq.py ma kod po wierszu 309 ( # If available, use C implementation), który robi dokładnie to, co opisuje komentarz.
tzot
3

Pozwala wybrać dowolną liczbę największych lub najmniejszych przedmiotów

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
źródło
3
Wytłumaczenie byłoby w porządku.
Peter Mortensen
Mój tytuł jest moim wyjaśnieniem
jasonleonhard
1
Moja odpowiedź jest dłuższa niż pytanie. Jakie wyjaśnienie chciałbyś dodać?
jasonleonhard
wikipedia.org/wiki/Min-max_heap i docs.python.org/3.0/library/heapq.html również mogą być pomocne.
jasonleonhard
2
Daje to poprawny wynik, ale tak naprawdę nie używa sterty, aby był wydajny. Dokument określa, że ​​nlargest i nsmallest sortują listę za każdym razem.
RossFabricant
3

Rozszerzenie klasy int i przesłonięcie __lt__ jest jednym ze sposobów.

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()
Gauraw
źródło
Jest to możliwe, ale wydaje mi się, że spowolniłoby to znacznie i wykorzystało dużo dodatkowej pamięci. MyInt nie może być również używany poza strukturą sterty. Ale dziękuję za wpisanie przykładu, który jest interesujący.
Leo Ufimtsev
Hah! Pewnego dnia po tym, jak skomentowałem, natknąłem się na sytuację, w której musiałem umieścić niestandardowy obiekt w stercie i potrzebowałem maksymalnego stosu. Naprawdę ponownie przeszukałem ten post i znalazłem twoją odpowiedź i oparłem na niej moje rozwiązanie. (Obiekt niestandardowy jest punktem o współrzędnych x, y i LT nadrzędne porównanie odległości od środka). Dziękuję za opublikowanie tego, głosowałem!
Leo Ufimtsev
1

Utworzyłem opakowanie sterty, które odwraca wartości, aby utworzyć stertę maksymalną, a także klasę opakowania dla sterty min, aby biblioteka była bardziej podobna do OOP. Tutaj sedno. Istnieją trzy klasy; Heap (klasa abstrakcyjna), HeapMin i HeapMax.

Metody:

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ɐɹƆ
źródło
0

W przypadku, gdy chcesz uzyskać największy element K za pomocą maksymalnej sterty, możesz wykonać następującą sztuczkę:

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
źródło
1
Niestety, złożoność czasowa w tym przypadku wynosi O (MlogM), gdzie M = len (nums), co jest sprzeczne z celem stosq. Zobacz implementację i komentarze nlargesttutaj -> github.com/python/cpython/blob/…
Arthur S
1
Dziękujemy za komentarz, na pewno sprawdzi załączony link.
RowanX
0

Idąc za doskonałą odpowiedzią Izaaka Turnera , chciałbym podać przykład oparty na K najbliższych punktach pochodzenia przy użyciu maksymalnego sterty.

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
źródło
0

Aby rozwinąć na https://stackoverflow.com/a/59311063/1328979 , oto w pełni udokumentowana, opatrzona adnotacjami i przetestowana implementacja języka Python 3 dla ogólnego przypadku.

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é
źródło
0

Jest to prosta MaxHeapimplementacja oparta na heapq. Chociaż działa tylko z wartościami liczbowymi.

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)

Stosowanie:

max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top())  # 5
Yuchen Zhong
źródło