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

heapsort python

Question

Python incluye el módulo heapq para min-montones, pero necesito un montón máximo. ¿Qué debería usar para una implementación de max-heap en Python?

Answer 1

Permitiéndole elegir una cantidad arbitraria de los 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]

Answer 2

He creado un envoltorio de heap que invierte los valores para crear un montón máximo, así como una clase contenedora para un montón mínimo para hacer que la biblioteca tenga más estilo OOP. Here 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

Answer 3

Implementé una versión máxima de heapq y la envié a PyPI. (Cambio muy leve del código heapq del 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: lo mismo 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

Answer 4

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.

Answer 5

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 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 se trata de un montón mínimo o máximo.

MinHeap, clases de MaxHeap

Agregar clases para 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"

Answer 6

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

Solo recuerde que cuando hace saltar un elemento para multiplicarlo con -1 nuevamente, para obtener el valor original nuevamente.

Answer 7

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 abrir elementos, utiliza:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap

Answer 8

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