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

Python incluye el módulo heapq para min-heaps, pero necesito un max heap. ¿Qué debo usar para una implementación de max-heap en Python?

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.

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 

La solución es negar sus valores cuando los almacena en el montón, o invertir la comparación de objetos de esta 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 max-heap:

 maxh = [] heapq.heappush(maxh,MaxHeapInt(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 está lidiando con un mínimo o máximo.

MinHeap, clases de MaxHeap

Agregar clases para los objetos MinHeap y MaxHeap 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" 

Multiplica los valores por -1, y ahí vas. Todos los números más altos son ahora los más bajos y viceversa.

Solo recuerda que cuando haces estallar un elemento para multiplicarlo por -1 nuevamente, para obtener el valor original nuevamente.

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

Le permite 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] 

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

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

He creado una envoltura de stack que invierte los valores para crear una stack máxima, así como una clase de envoltura para una stack min para hacer que la biblioteca sea más parecida a la POO. 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 

Extender 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()