heapq с настраиваемым предикатом сравнения

Я пытаюсь создать кучу с настраиваемым предикатом сортировки. Поскольку входящие в него значения относятся к «определяемому пользователем» типу, я не могу изменить их встроенный предикат сравнения.

Есть ли способ сделать что-то вроде:

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

Или, что еще лучше, я мог бы обернуть функции heapq в свой собственный контейнер, чтобы мне не нужно было передавать предикат.

Согласно документации heapq , способ настроить порядок кучи - сделать так, чтобы каждый элемент в куче был кортежем, причем первый элемент кортежа был тем, который принимает обычные сравнения Python.

Функции в модуле heapq немного громоздки (поскольку они не объектно-ориентированы) и всегда требуют, чтобы наш объект кучи (список с динамической памятью) явно передавался в качестве первого параметра. Мы можем убить двух зайцев одним выстрелом, создав очень простой класс-оболочку, который позволит нам указать keyфункцию и представить кучу как объект.

В приведенном ниже классе хранится внутренний список, в котором каждый элемент является кортежем, первый член которого является ключом, вычисляемым во время вставки элемента с использованием keyпараметра, переданного при создании экземпляра кучи:

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

(Дополнительная self.indexчасть состоит в том, чтобы избежать конфликтов, когда оцененное значение ключа является ничьей, а сохраненное значение не может быть напрямую сопоставлено - иначе heapq может завершиться ошибкой с TypeError)

Определите класс, в котором переопределите __lt__()функцию. См. Пример ниже (работает в 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]

Документация по heapq предполагает, что элементы кучи могут быть кортежами, в которых первый элемент является приоритетным и определяет порядок сортировки.

Однако более уместным для вашего вопроса является то, что документация включает обсуждение с образцом кода того, как можно реализовать свои собственные функции оболочки heapq для решения проблем стабильности сортировки и элементов с равным приоритетом (среди других проблем).

Вкратце, их решение состоит в том, чтобы каждый элемент в heapq был тройкой с приоритетом, количеством записей и элементом, который нужно вставить. Счетчик записей гарантирует, что элементы с одинаковым приоритетом a отсортированы в том порядке, в котором они были добавлены в heapq.

Ограничение обоих ответов состоит в том, что они не позволяют рассматривать связи как связи. В первом случае связи разрываются путем сравнения элементов, во втором - путем сравнения порядка ввода. Гораздо быстрее позволить связям быть связями, и если их будет много, это может иметь большое значение. Исходя из вышеизложенного и из документации, неясно, можно ли этого достичь в heapq. Кажется странным, что heapq не принимает ключ, в то время как функции, производные от него в том же модуле, принимают.
PS: Если вы перейдете по ссылке в первом комментарии («возможный дубликат ...»), есть еще одно предложение по определению файла, которое кажется решением.

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

Используйте это для сравнения значений объектов в heapq