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

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

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

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

Installation

pip install heapq_max

Utilisation

tl;dr : même chose que le module heapq sauf que l'on ajoute '_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

Answer 2

Il s'agit d'un simple MaxHeap sur la base de heapq . Bien qu'il 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)

Utilisation :

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

Answer 3

J'avais également besoin d'utiliser un max-heap, et je traitais des nombres entiers, donc j'ai simplement enveloppé les deux méthodes dont j'avais besoin à partir de heap comme suit :

import heapq

def heappush(heap, item):
    return heapq.heappush(heap, -item)

def heappop(heap):
    return -heapq.heappop(heap)

Et puis j'ai juste remplacé mon heapq.heappush() y heapq.heappop() appels avec heappush() y heappop() respectivement.

Answer 4

Si vous insérez des clés qui sont comparables, mais pas de type int, vous pouvez potentiellement remplacer les opérateurs de comparaison sur eux (c'est-à-dire que <= devient > et > devient <=). Sinon, vous pouvez remplacer heapq._siftup dans le module heapq (ce n'est que du code Python, en fin de compte).

Answer 5

Extension de la classe int et surcharge Je ne sais pas. est l'un des moyens.

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