libreria - priority queue python

heapq con predicado de comparación personalizado

Question

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

¿Hay alguna manera de hacer algo como esto?

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

O mejor aún, podría ajustar las funciones de heapq en mi propio contenedor para no tener que pasar el predicado.

Answer 1

De acuerdo con la documentación de heapq , la forma de personalizar el orden de montón es hacer que cada elemento en el montón sea una tupla, con el primer elemento de tupla que acepta 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 heap (una lista heapified) pase explícitamente como el primer parámetro. Podemos matar dos pájaros de un tiro creando una clase contenedora muy simple que nos permita especificar una función key y presentar el montón como un objeto.

La clase a continuación contiene 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 , 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
       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]

Answer 2

La documentación de heapq sugiere que los elementos de 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 un código de ejemplo de cómo uno podría implementar sus propias funciones de contenedor heapq para tratar los problemas de estabilidad de clasificación y elementos con igual prioridad (entre otros problemas).

En pocas palabras, su solución es tener cada elemento en el heapq sea un triple con la prioridad, un conteo de entrada 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.

Answer 3

La limitación con ambas respuestas es que no permiten que los lazos se traten como vínculos. En el primero, los vínculos se rompen al comparar elementos, en el segundo al comparar el orden de entrada. Es más rápido dejar que los lazos sean lazos, y si hay muchos, podría hacer una gran diferencia. En función de lo anterior y de 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 sigues el enlace en el primer comentario ("posible duplicado ...") hay otra sugerencia de definir le que parece ser una solución.