heapq con predicado de comparación personalizado

Estoy tratando de construir un montón con un predicado de clasificación personalizado. Dado que los valores que entran en él son del tipo 'definido por el usuario', no puedo modificar su predicado de comparación incorporado.

¿Hay alguna forma de hacer algo como:

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

O incluso mejor, podría envolver las funciones de heapq en mi propio contenedor para no tener que seguir pasando el predicado.

Según la documentación de heapq , la forma de personalizar el orden del montón es hacer que cada elemento del montón sea una tupla, siendo el primer elemento de tupla uno que acepte las comparaciones normales de Python.

Las funciones en el módulo heapq son un poco engorrosas (ya que no están orientadas a objetos), y siempre requieren que nuestro objeto de pila (una lista en pila) se pase explícitamente como primer parámetro. Podemos matar dos pájaros de un tiro creando una clase contenedora muy simple que nos permitirá especificar unkey función y presentar el montón como un objeto.

La siguiente clase mantiene una lista interna, donde cada elemento es una tupla, el primer miembro de la cual es una clave, calculada en el momento de la inserción del elemento usando el keyparámetro, pasado en la instanciación de 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]

(La self.indexparte adicional es evitar conflictos cuando el valor clave evaluado es un empate y el valor almacenado no es directamente comparable; de ​​lo contrario, heapq podría fallar con TypeError)

Defina una clase, en la que anule la __lt__()función. Vea el ejemplo a continuación (funciona en 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]

La documentación de heapq sugiere que los elementos del montón podrían ser tuplas en las que el primer elemento es la prioridad y define el orden de clasificación.

Más pertinente a su pregunta, sin embargo, es que la documentación incluye una discusión con código de muestra de cómo uno podría implementar sus propias funciones de contenedor de heapq para lidiar con los problemas de estabilidad de ordenamiento y elementos con igual prioridad (entre otros temas).

En pocas palabras, su solución es que cada elemento en el montón sea un triple con la prioridad, un recuento de entradas y el elemento que se va a insertar. El recuento de entradas garantiza que los elementos con la misma prioridad se clasifiquen en el orden en que se agregaron al heapq.

La limitación de ambas respuestas es que no permiten que los vínculos se traten como vínculos. En el primero, los vínculos se rompen comparando elementos, en el segundo comparando el orden de entrada. Es más rápido dejar que los lazos sean lazos, y si hay muchos, podría marcar una gran diferencia. Según lo anterior y los documentos, no está claro si esto se puede lograr en heapq. Parece extraño que heapq no acepte una clave, mientras que las funciones derivadas de ella en el mismo módulo sí lo hacen.
PD: Si sigue el enlace en el primer comentario ("posible duplicado ...") hay otra sugerencia de definir el archivo que parece una solución.

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

Use esto para comparar valores de objetos en heapq