Que dois-je utiliser pour une implémentation de max-heap en Python ?

Question

Python inclut le module heapq pour les min-heaps, mais j'ai besoin d'un max heap. Que dois-je utiliser pour une implémentation du max-heap en Python ?

Answer 1

Le moyen le plus simple est d'inverser la valeur des clés et d'utiliser heapq. Par exemple, transformez 1000.0 en -1000.0 et 5.0 en -5.0.

Answer 2

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 voulez ensuite faire sauter des éléments, utilisez :

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

Answer 3

La solution est de nier vos valeurs lorsque vous les stockez dans le tas, ou d'inverser votre comparaison d'objets 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 max-heap :

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ésenvelopper vos valeurs, ce qui nécessite de savoir si vous avez affaire à un tas min ou max.

Classes MinHeap, MaxHeap

Ajout de classes pour MinHeap y MaxHeap peuvent 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"

Answer 4

La solution la plus simple et idéale

Multipliez les valeurs par -1

Et voilà. Tous les chiffres les plus élevés sont maintenant les plus bas et vice versa.

N'oubliez pas que lorsque vous faites sauter un élément, vous devez le multiplier par -1 afin de retrouver la valeur originale.

Answer 5

Le moyen le plus simple est de convertir chaque élément en négatif et cela résoudra votre problème.

import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)

Le résultat sera le suivant :

[-20, -1, -10]