heapq z niestandardowym predykatem porównania

Próbuję zbudować stertę z niestandardowym predykatem sortowania. Ponieważ wartości wchodzące w to są typu „zdefiniowanego przez użytkownika”, nie mogę zmodyfikować ich wbudowanego predykatu porównania.

Czy jest sposób na zrobienie czegoś takiego:

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

Albo jeszcze lepiej, mógłbym zawinąć funkcje heapq we własnym kontenerze, więc nie muszę dalej przekazywać predykatu.

Zgodnie z dokumentacją heapq , sposobem dostosowania kolejności sterty jest ustawienie każdego elementu na stercie jako krotki, przy czym pierwszy element krotki to taki, który akceptuje zwykłe porównania w Pythonie.

Funkcje w module heapq są nieco kłopotliwe (ponieważ nie są zorientowane obiektowo) i zawsze wymagają, aby nasz obiekt sterty (lista sterty) był jawnie przekazany jako pierwszy parametr. Możemy upiec dwie pieczenie na jednym ogniu, tworząc bardzo prostą klasę opakowującą, która pozwoli nam określić keyfunkcję i przedstawić stertę jako obiekt.

Poniższa klasa przechowuje wewnętrzną listę, w której każdy element jest krotką, której pierwszym składnikiem jest klucz, obliczany w czasie wstawiania elementu za pomocą keyparametru, przekazywany w instancji Heap:

# -*- 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]

(Dodatkową self.indexczęścią jest uniknięcie kolizji, gdy oszacowana wartość klucza jest remisem, a przechowywana wartość nie jest bezpośrednio porównywalna - w przeciwnym razie heapq może zawieść z TypeError)

Zdefiniuj klasę, w której nadpisujemy __lt__()funkcję. Zobacz przykład poniżej (działa w Pythonie 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]

Dokumentacja heapq sugeruje, że elementy sterty mogą być krotkami, w których pierwszy element jest priorytetem i definiuje kolejność sortowania.

Bardziej istotne dla twojego pytania jest jednak to, że dokumentacja zawiera dyskusję z przykładowym kodem, w jaki sposób można zaimplementować własne funkcje opakowujące heapq, aby poradzić sobie z problemami stabilności sortowania i elementami o równym priorytecie (między innymi).

W skrócie, ich rozwiązanie polega na tym, aby każdy element w heapq był potrójny z priorytetem, liczbą wpisów i elementem do wstawienia. Liczba pozycji gwarantuje, że elementy o tym samym priorytecie a posortowane w kolejności, w jakiej zostały dodane do heapq.

Ograniczeniem obu odpowiedzi jest to, że nie pozwalają one na traktowanie krawatów jako remisów. W pierwszej więzi są rozwiązywane przez porównywanie elementów, w drugiej przez porównywanie kolejności wprowadzania. Szybciej jest po prostu pozwolić, aby krawaty były wiązaniami, a jeśli jest ich dużo, może to mieć duże znaczenie. Na podstawie powyższego i dokumentacji nie jest jasne, czy można to osiągnąć w heapq. Wydaje się dziwne, że heapq nie akceptuje klucza, podczas gdy funkcje wyprowadzone z niego w tym samym module tak.
PS: Jeśli klikniesz link w pierwszym komentarzu ("możliwy duplikat ..."), pojawi się kolejna sugestia zdefiniowania pliku, która wydaje się rozwiązaniem.

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

Użyj tego do porównania wartości obiektów w heapq