¿Qué uso para una implementación max-heap en Python?

Respuestas:

244

La forma más fácil es invertir el valor de las claves y usar heapq. Por ejemplo, convierta 1000.0 en -1000.0 y 5.0 en -5.0.

Daniel Stutzbach
fuente
38
También es la solución estándar.
Andrew McGregor
44
uggh; Kludge total. Me sorprende heapqque no proporcione un reverso.
shabbychef
40
Guau. Estoy sorprendido de que esto no sea proporcionado por heapq, y que no haya una buena alternativa.
ire_and_curses
23
@gatoatigrado: Si tiene algo que no se asigna fácilmente a int/ float, puede invertir el orden envolviéndolos en una clase con un __lt__operador invertido .
Daniel Stutzbach
55
@Aerovistae se aplica el mismo consejo: invierta los valores (es decir, cambie el signo) independientemente de si es positivo o negativo para empezar.
Dennis
235

Puedes usar

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 luego quieres hacer estallar elementos, usa:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
Lijo Joseph
fuente
34
Parece que hay algunas funciones no documentadas de almacenamiento dinámico máximo: _heapify_max, _heappushpop_max, _siftdown_max, y _siftup_max.
ziyuang
127
Guau. Estoy sorprendido de que no ES tales incorporado en solución en heapq. Pero entonces es totalmente razonable que se NO incluso ligeramente menciona en absoluto en el documento oficial! WTF!
RayLuo
27
Cualquiera de las funciones pop / push rompe la estructura de almacenamiento dinámico máximo, por lo que este método no es factible.
Siddhartha
22
NO LO USES. Como LinMa y Siddhartha notaron, push / pop rompe el orden.
Alex Fedulov
13
Los métodos que comienzan con un guión bajo son privados y se pueden eliminar sin previo aviso . No los uses.
user4815162342
66

La solución es negar sus valores cuando los almacena en el montón, o invertir su comparación de objetos de la siguiente manera:

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)

Ejemplo de un montón máximo:

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

Pero debe recordar envolver y desenvolver sus valores, lo que requiere saber si se trata de un montón mínimo o máximo.

Clases MinHeap, MaxHeap

Agregar clases para MinHeapy MaxHeapobjetos puede simplificar su código:

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

Ejemplo de uso:

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
fuente
Agradable. Tomé esto y agregué un listparámetro opcional a __init__ en cuyo caso llamo heapq.heapifyy también agregué un heapreplacemétodo.
Booboo
1
Sorprendido de que nadie haya captado este error tipográfico: MaxHeapInt -> MaxHeapObj. De lo contrario, una solución muy limpia de hecho.
Chiraz BenAbdelkader
@ChirazBenAbdelkader solucionado, gracias.
Isaac Turner
39

La solución más fácil e ideal.

Multiplica los valores por -1

Ahí tienes. Todos los números más altos son ahora los más bajos y viceversa.

Solo recuerde que cuando hace estallar un elemento para multiplicarlo por -1 para obtener el valor original nuevamente.

Sebastian Nielsen
fuente
Genial, pero la mayoría de las soluciones son compatibles con las clases / otros tipos, y no cambiarán los datos reales. La pregunta abierta es si multiplicar el valor por -1 no los cambiará (flotante extremadamente preciso).
Alex Baranowski
1
@AlexBaranowski. Eso es cierto, pero esa ha sido la respuesta del mantenedor: bugs.python.org/issue27295
Flair
Los encargados del mantenimiento tienen derecho a no implementar alguna funcionalidad, pero esta IMO es realmente útil.
Alex Baranowski
7

Implementé una versión heap max de heapq y la envié a PyPI. (Muy ligero cambio del código CPython del módulo heapq.)

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

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

Instalación

pip install heapq_max

Uso

tl; dr: igual que el módulo heapq excepto que agrega '_max' a todas las funciones.

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
fuente
4

Si está insertando claves que son comparables pero no de tipo int, podría anular los operadores de comparación (es decir, <= convertirse> y> se convierte en <=). De lo contrario, puede anular heapq._siftup en el módulo heapq (al final, todo es solo código Python).

rlotun
fuente
99
“Todo es solo código Python”: depende de la versión e instalación de Python. Por ejemplo, mi heapq.py instalado tiene un código después de la línea 309 ( # If available, use C implementation) que hace exactamente lo que describe el comentario.
tzot
3

Permitiéndole elegir una cantidad arbitraria de artículos más grandes o más pequeños

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
fuente
3
Una explicación estaría en orden.
Peter Mortensen
Mi título es mi explicación
jasonleonhard
1
Mi respuesta es más larga que la pregunta. ¿Qué explicación te gustaría agregar?
jasonleonhard
wikipedia.org/wiki/Min-max_heap y docs.python.org/3.0/library/heapq.html también pueden ser de alguna ayuda.
jasonleonhard
2
Esto da el resultado correcto pero en realidad no usa un montón para hacerlo eficiente. El documento especifica que nlargest y nsmallest ordenan la lista cada vez.
RossFabricant
3

Ampliar la clase int y anular __lt__ es una de las formas.

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
fuente
Es posible, pero siento que ralentizaría mucho las cosas y usaría mucha memoria extra. MyInt tampoco se puede usar realmente fuera de la estructura de almacenamiento dinámico. Pero gracias por escribir un ejemplo, es interesante verlo.
Leo Ufimtsev
Ja! Un día después de comentar me encontré con la situación en la que necesitaba poner un objeto personalizado en un montón y necesitaba un montón máximo. Realmente busqué en Google esta publicación y encontré su respuesta y basé mi solución en ella. (El objeto personalizado es un punto con x, coordenada y lt anulando la distancia de comparación desde el centro). Gracias por publicar esto, ¡he votado!
Leo Ufimtsev
1

He creado un contenedor de montón que invierte los valores para crear un montón máximo, así como una clase de contenedor para un montón mínimo para hacer que la biblioteca sea más parecida a OOP. Aquí está la esencia. Hay tres clases; Heap (clase abstracta), HeapMin y HeapMax.

Métodos:

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

En caso de que desee obtener el elemento K más grande utilizando el montón máximo, puede hacer el siguiente truco:

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
fuente
1
Desafortunadamente, la complejidad de tiempo para esto es O (MlogM) donde M = len (nums), lo que anula el propósito de heapq. Vea la implementación y los comentarios nlargestaquí -> github.com/python/cpython/blob/…
Arthur S
1
Gracias por su comentario informativo, asegúrese de revisar el enlace adjunto.
RowanX
0

Siguiendo la excelente respuesta de Isaac Turner , me gustaría poner un ejemplo basado en K Puntos más cercanos al origen usando el montón máximo.

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
fuente
0

Para profundizar en https://stackoverflow.com/a/59311063/1328979 , aquí hay una implementación de Python 3 completamente documentada, comentada y probada para el caso general.

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é
fuente
0

Esta es una MaxHeapimplementación simple basada en heapq. Aunque solo funciona con valores numéricos.

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)

Uso:

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