Qu'est-ce que j'utilise pour une implémentation max-heap en Python?

Réponses:

244

Le moyen le plus simple consiste à inverser la valeur des clés et à utiliser heapq. Par exemple, transformez 1000,0 en -1000,0 et 5,0 en -5,0.

Daniel Stutzbach
la source
38
C'est aussi la solution standard.
Andrew McGregor
44
uggh; kludge total. Je suis surpris de heapqne pas fournir un revers.
shabbychef
40
Sensationnel. Je suis étonné que cela ne soit pas fourni par heapqet qu'il n'y ait pas de bonne alternative.
ire_and_curses
23
@gatoatigrado: Si vous avez quelque chose qui ne mappe pas facilement vers int/ float, vous pouvez inverser l'ordre en les enveloppant dans une classe avec un __lt__opérateur inversé .
Daniel Stutzbach
5
@Aerovistae, le même conseil s'applique: inversez les valeurs (c.-à-d. Changez de signe), que ce soit positif ou négatif pour commencer.
Dennis
235

Vous pouvez utiliser

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

Si vous souhaitez ensuite faire apparaître des éléments, utilisez:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
Lijo Joseph
la source
34
On dirait qu'il ya des fonctions non documentées pour tas max: _heapify_max, _heappushpop_max, _siftdown_maxet _siftup_max.
ziyuang
127
Sensationnel. Je suis étonné qu'il EST un tel intégré en solution dans heapq. Mais alors il est totalement déraisonnable qu'il ne soit PAS même légèrement mentionné du tout dans le document officiel! WTF!
RayLuo
27
Aucune des fonctions pop / push ne casse la structure du tas max, donc cette méthode n'est pas faisable.
Siddhartha
22
NE L'UTILISE PAS. Comme LinMa et Siddhartha l'ont remarqué, push / pop rompt l'ordre.
Alex Fedulov
13
Les méthodes commençant par un trait de soulignement sont privées et peuvent être supprimées sans préavis . Ne les utilisez pas.
user4815162342
66

La solution consiste à annuler vos valeurs lorsque vous les stockez dans le tas ou à inverser votre comparaison d'objet comme suit:

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)

Exemple d'un tas max:

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

Mais vous devez vous rappeler d'envelopper et de déballer vos valeurs, ce qui nécessite de savoir si vous avez affaire à un tas min ou max.

Classes MinHeap, MaxHeap

L'ajout de classes pour MinHeapet d' MaxHeapobjets peut simplifier votre code:

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

Exemple d'utilisation:

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
la source
Agréable. J'ai pris cela et ajouté un listparamètre facultatif à __init__ auquel cas j'appelle heapq.heapifyet j'ai également ajouté une heapreplaceméthode.
Booboo
1
Surpris que personne n'ait attrapé cette faute de frappe: MaxHeapInt -> MaxHeapObj. Sinon, une solution très propre en effet.
Chiraz BenAbdelkader
@ChirazBenAbdelkader corrigé, merci.
Isaac Turner
39

La solution la plus simple et idéale

Multipliez les valeurs par -1

Voilà. Tous les nombres les plus élevés sont désormais les plus bas et vice versa.

N'oubliez pas que lorsque vous éclatez un élément pour le multiplier par -1 afin d'obtenir à nouveau la valeur d'origine.

Sebastian Nielsen
la source
Très bien, mais la plupart des solutions prennent en charge les classes / autres types et ne changeront pas les données réelles. La question ouverte est de savoir si la multiplication de la valeur par -1 ne les changera pas (flottant extrêmement précis).
Alex Baranowski
1
@AlexBaranowski. C'est vrai, mais c'est la réponse du mainteneur: bugs.python.org/issue27295
Flair
Les responsables de puits ont le droit de ne pas implémenter certaines fonctionnalités, mais celui-ci IMO est en fait utile.
Alex Baranowski
7

J'ai implémenté une version max heap de heapq et l'ai soumise à PyPI. (Très léger changement de code CPython du module heapq.)

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

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

Installation

pip install heapq_max

Usage

tl; dr: identique au module heapq sauf en ajoutant '_max' à toutes les fonctions.

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
la source
4

Si vous insérez des clés comparables mais pas de type int, vous pouvez potentiellement remplacer les opérateurs de comparaison sur celles-ci (c'est-à-dire <= devenir> et> devient <=). Sinon, vous pouvez remplacer heapq._siftup dans le module heapq (c'est tout simplement du code Python, à la fin).

rlotun
la source
9
«C'est tout simplement du code Python»: cela dépend de votre version et de votre installation Python. Par exemple, mon heapq.py installé a du code après la ligne 309 ( # If available, use C implementation) qui fait exactement ce que le commentaire décrit.
2010
3

Vous permettant de choisir une quantité arbitraire d'articles les plus grands ou les plus petits

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
la source
3
Une explication serait de mise.
Peter Mortensen
Mon titre est mon explication
jasonleonhard
1
Ma réponse est plus longue que la question. Quelle explication aimeriez-vous ajouter?
jasonleonhard
wikipedia.org/wiki/Min-max_heap et docs.python.org/3.0/library/heapq.html pourraient également être utiles.
jasonleonhard
2
Cela donne le résultat correct mais n'utilise pas réellement un tas pour le rendre efficace. Le document spécifie que nlargest et nsmallest trient la liste à chaque fois.
RossFabricant
3

Étendre la classe int et remplacer __lt__ est l'une des façons.

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
la source
C'est possible, mais j'ai l'impression que cela ralentirait beaucoup les choses et utiliserait beaucoup de mémoire supplémentaire. MyInt ne peut pas non plus être vraiment utilisé en dehors de la structure de tas. Mais merci d'avoir tapé un exemple, c'est intéressant à voir.
Leo Ufimtsev
Hah! Un jour après avoir commenté, je suis tombé sur la situation où je devais mettre un objet personnalisé dans un tas et j'avais besoin d'un tas max. J'ai en fait re-googlé ce post et trouvé votre réponse et basé ma solution sur celui-ci. (L'objet personnalisé étant un point avec les coordonnées x, y et lt remplaçant la comparaison de la distance par rapport au centre). Merci d'avoir posté ceci, j'ai voté!
Leo Ufimtsev
1

J'ai créé un wrapper de tas qui inverse les valeurs pour créer un max-heap, ainsi qu'une classe de wrapper pour un min-heap pour rendre la bibliothèque plus proche de la POO. Voici l'essentiel. Il y a trois classes; Heap (classe abstraite), HeapMin et HeapMax.

Méthodes:

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ɐɹƆ
la source
0

Si vous souhaitez obtenir le plus grand élément K en utilisant le tas max, vous pouvez faire l'astuce suivante:

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
la source
1
Malheureusement, la complexité temporelle pour cela est O (MlogM) où M = len (nums), ce qui va à l'encontre du but de heapq. Voir l'implémentation et les commentaires nlargestici -> github.com/python/cpython/blob/…
Arthur S
1
Merci pour votre commentaire informatif, assurez-vous de vérifier le lien ci-joint.
RowanX
0

Suite à l'excellente réponse d'Isaac Turner , j'aimerais mettre un exemple basé sur K points les plus proches de l'origine en utilisant le tas max.

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
la source
0

Pour élaborer sur https://stackoverflow.com/a/59311063/1328979 , voici une implémentation Python 3 entièrement documentée, annotée et testée pour le cas général.

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é
la source
0

Il s'agit d'une MaxHeapimplémentation simple basée sur heapq. Bien que cela ne fonctionne qu'avec des valeurs numériques.

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)

Usage:

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