heapq con predicado de comparación personalizado

Estoy tratando de construir un montón con un predicado de orden personalizado. Dado que los valores que se incluyen son del tipo ‘definido por el usuario’, no puedo modificar su predicado de comparación incorporado.

¿Hay una manera 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 heapq en mi propio contenedor, por lo que no necesito seguir pasando el predicado.

De acuerdo con 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 la tupla uno que acepte las comparaciones normales de Python.

Las funciones en el módulo heapq son un poco incómodas (ya que no están orientadas a objetos), y siempre requieren que nuestro objeto de stack (una lista heapified) se pase explícitamente como primer parámetro. Podemos matar dos pájaros de un tiro creando una clase de envoltura muy simple que nos permitirá especificar una función key 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 utilizando el parámetro key , aprobada 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 if initial: self._data = [(key(item), item) for item in initial] heapq.heapify(self._data) else: self._data = [] def push(self, item): heapq.heappush(self._data, (self.key(item), item)) def pop(self): return heapq.heappop(self._data)[1] 

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.

Sin embargo, lo más pertinente a su pregunta es que la documentación incluye una discusión con código de ejemplo de cómo se podrían implementar sus propias funciones de envoltura de heapq para tratar los problemas de la estabilidad de clasificación y los elementos con la misma prioridad (entre otras cuestiones).

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

La limitación con 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 los lazos, y si hay muchos de ellos, puede hacer una gran diferencia. Basado en lo anterior y en 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 del primer comentario (“posible duplicado …”), hay otra sugerencia de definir el archivo que parece ser una solución.