heapq con predicado de comparación personalizado

82

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.

vsekhar
fuente

Respuestas:

120

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)

jsbueno
fuente
4
¡Muy agradable! Incluso podría ir más allá y usar triples (self.key (elemento), id, elemento), donde id podría ser un número entero manejado como un atributo de clase, e incrementado después de cada pulsación. De esa manera, evita la excepción que se genera cuando key (item1) = key (item2). Porque las claves serían únicas.
Zeycus
4
De hecho, intenté empujar esto (o algo basado en esto) en stdlib de Python, y la sugerencia fue rechazada.
jsbueno
1
lástima, se ajusta al estilo orientado a objetos de la mayoría de las funciones de Python, y el argumento clave proporciona flexibilidad adicional.
Zeycus
He usado list en lugar de tupla para, por ejemplo, [self.key (item), id, item] y funciona bien siempre que el primer índice sea key.
Deepak Yadav
5
Esto fallaría si los elementos no son comparables y existen vínculos en los valores clave. Pondría id(item)como elemento medio de la tupla para romper los lazos.
Georgi Yanchev
47

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]

Fanchen Bao
fuente
4
¡Esta parece ser la solución más limpia con diferencia!
Roymunson
Totalmente de acuerdo con los dos comentarios anteriores. Esta parece ser una solución mejor y más limpia para Python 3.
Chiraz BenAbdelkader
Además, aquí hay una solución muy similar a una pregunta similar: stackoverflow.com/questions/2501457/…
Chiraz BenAbdelkader
1
Probé esto usando en su __gt__lugar y también funciona. ¿Por qué no importa qué método mágico usemos? No puedo encontrar nada en heapqla documentación de. ¿Quizás esté relacionado con cómo Python hace las comparaciones en general?
Josh Clark
1
Al hacer una comparación en heapq, Python busca __lt__()primero. Si no está definido, buscará __gt__(). Si no se define ninguno, lanza TypeError: '<' not supported between instances of 'Node' and 'Node'. Esto se puede confirmar definiendo ambos __lt__()y __gt__(), colocando una declaración impresa en cada uno y teniendo __lt__()retorno NotImplemented.
Fanchen Bao
19

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.

srgerg
fuente
Esta es la solución correcta, tanto heappush como heappushpop funcionan directamente con tuplas
daisy
2

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.

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

Use esto para comparar valores de objetos en heapq

Ritika Gupta
fuente