Heapq mit benutzerdefiniertem Vergleichsprädikat

Ich versuche, einen Heap mit einem benutzerdefinierten Sortierprädikat zu erstellen. Da die darin enthaltenen Werte vom Typ 'Benutzerdefiniert' sind, kann ich das integrierte Vergleichsprädikat nicht ändern.

Gibt es eine Möglichkeit, etwas zu tun wie:

h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)

Oder noch besser, ich könnte die Heapq-Funktionen in meinen eigenen Container packen, damit ich das Prädikat nicht weiter übergeben muss.

Gemäß der Heapq-Dokumentation besteht die Möglichkeit, die Heap-Reihenfolge anzupassen, darin, dass jedes Element auf dem Heap ein Tupel ist, wobei das erste Tupelelement eines ist, das normale Python-Vergleiche akzeptiert.

Die Funktionen im Heapq-Modul sind etwas umständlich (da sie nicht objektorientiert sind) und erfordern immer, dass unser Heap-Objekt (eine Heapified-Liste) explizit als erster Parameter übergeben wird. Wir können zwei Fliegen mit einer Klappe schlagen, indem wir eine sehr einfache Wrapper-Klasse erstellen, mit der wir eine keyFunktion angeben und den Heap als Objekt präsentieren können.

Die folgende Klasse führt eine interne Liste, in der jedes Element ein Tupel ist, dessen erstes Mitglied ein Schlüssel ist, der zum Zeitpunkt des Einfügens des Elements unter Verwendung des keyParameters berechnet wird und bei der Heap-Instanziierung übergeben wird:

# -*- coding: utf-8 -*-
import heapq

class MyHeap(object):
   def __init__(self, initial=None, key=lambda x:x):
       self.key = key
       self.index = 0
       if initial:
           self._data = [(key(item), i, item) for i, item in enumerate(initial)]
           self.index = len(self._data)
           heapq.heapify(self._data)
       else:
           self._data = []

   def push(self, item):
       heapq.heappush(self._data, (self.key(item), self.index, item))
       self.index += 1

   def pop(self):
       return heapq.heappop(self._data)[2]

(Der zusätzliche self.indexTeil besteht darin, Konflikte zu vermeiden, wenn der ausgewertete Schlüsselwert ein Unentschieden ist und der gespeicherte Wert nicht direkt vergleichbar ist. Andernfalls könnte heapq mit TypeError fehlschlagen.)

Definieren Sie eine Klasse, in der die __lt__()Funktion überschrieben wird. Siehe Beispiel unten (funktioniert in Python 3.7):

import heapq

class Node(object):
    def __init__(self, val: int):
        self.val = val

    def __repr__(self):
        return f'Node value: {self.val}'

    def __lt__(self, other):
        return self.val < other.val

heap = [Node(2), Node(0), Node(1), Node(4), Node(2)]
heapq.heapify(heap)
print(heap)  # output: [Node value: 0, Node value: 2, Node value: 1, Node value: 4, Node value: 2]

heapq.heappop(heap)
print(heap)  # output: [Node value: 1, Node value: 2, Node value: 2, Node value: 4]

Die Heapq-Dokumentation schlägt vor, dass Heap-Elemente Tupel sein können, bei denen das erste Element die Priorität hat, und definiert die Sortierreihenfolge.

Relevanter für Ihre Frage ist jedoch, dass die Dokumentation eine Diskussion mit Beispielcode enthält, wie man seine eigenen Heapq-Wrapper-Funktionen implementieren kann, um die Probleme der Sortierstabilität und Elemente mit gleicher Priorität (unter anderem) zu lösen.

Kurz gesagt, ihre Lösung besteht darin, dass jedes Element im Heapq ein Tripel mit der Priorität, der Anzahl der Einträge und dem einzufügenden Element ist. Die Anzahl der Einträge stellt sicher, dass Elemente mit derselben Priorität in der Reihenfolge sortiert werden, in der sie dem Heapq hinzugefügt wurden.

Die Einschränkung bei beiden Antworten besteht darin, dass sie nicht zulassen, dass Bindungen als Bindungen behandelt werden. Im ersten Fall werden Bindungen durch Vergleichen von Elementen unterbrochen, im zweiten Fall durch Vergleichen der Eingabereihenfolge. Es ist schneller, Krawatten einfach Krawatten sein zu lassen, und wenn es viele davon gibt, könnte dies einen großen Unterschied machen. Aufgrund der obigen Ausführungen und der Dokumente ist nicht klar, ob dies in heapq erreicht werden kann. Es scheint seltsam, dass heapq keinen Schlüssel akzeptiert, während von ihm im selben Modul abgeleitete Funktionen dies tun.
PS: Wenn Sie dem Link im ersten Kommentar folgen ("mögliches Duplikat ..."), gibt es einen weiteren Vorschlag, le zu definieren, der wie eine Lösung erscheint.

setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)

Verwenden Sie diese Option, um Werte von Objekten in heapq zu vergleichen