heapq - max heap python

¿Cómo hacer que heapq evalúe el montón de un atributo específico?

Question

Deseo contener un montón de objetos, no solo números. Tendrán un atributo de enteros en ellos que el montón puede ordenar por. La forma más fácil de usar montones en python es heapq, pero ¿cómo le digo que clasifique por un atributo específico cuando se usa heapq?

Answer 1

De acuerdo con el Documento Oficial , una solución a esto es almacenar las entradas como tuplas (por favor, eche un vistazo a las Secciones 8.4.1 y 8.4.2 ).

Por ejemplo, su objeto es algo así en el formato de tupla (clave, valor_1, valor_2)

Cuando pones los objetos (es decir, las tuplas ) en un montón , se comparará el primer atributo en el objeto (en este caso es la clave ) para comparar. Si ocurre un empate, Heap usará el siguiente atributo (es decir, value_1 ) y así sucesivamente.

Por ejemplo:

import heapq

heap = []
heapq.heappush(heap, (0,''one'', 1))
heapq.heappush(heap, (1,''two'', 11))
heapq.heappush(heap, (1, ''two'', 2))
heapq.heappush(heap, (1, ''one'', 3))
heapq.heappush(heap, (1,''two'', 3))
heapq.heappush(heap, (1,''one'', 4))
heapq.heappush(heap, (1,''two'', 5))
heapq.heappush(heap, (1,''one'', 1))

show_tree(heap)

Salida:

                                      (0, ''one'', 1)                                       
                (1, ''one'', 1)                                (1, ''one'', 4)                
    (1, ''one'', 3)         (1, ''two'', 3)         (1, ''two'', 2)         (1, ''two'', 5)     
(1, ''two'', 11)

Acerca de imprimir bastante un montón en python: show_tree()

Answer 2

De acuerdo con el ejemplo de la documentation , puede usar tuplas y ordenará según el primer elemento de la tupla:

>>> h = []
>>> heappush(h, (5, ''write code''))
>>> heappush(h, (7, ''release product''))
>>> heappush(h, (1, ''write spec''))
>>> heappush(h, (3, ''create tests''))
>>> heappop(h)
(1, ''write spec'')

Entonces, si no quiere (¿o no puede?) Hacer un método __cmp__ , puede extraer manualmente su clave de clasificación en el momento del __cmp__ .

Tenga en cuenta que si los primeros elementos en un par de tuplas son iguales, se compararán más elementos. Si esto no es lo que desea, debe asegurarse de que cada primer elemento sea único.

Answer 3

Lamentablemente, no se puede, aunque esta es una función que a menudo se solicita.

Una opción sería insertar tuplas (clave, valor) en el montón. Sin embargo, eso no funcionará si los valores arrojan una excepción cuando se comparan (se compararán en el caso de un empate entre las claves).

Una segunda opción sería definir un __lt__ (menor que) en la clase que usará el atributo apropiado para comparar los elementos para la clasificación. Sin embargo, eso podría no ser posible si los objetos fueron creados por otro paquete o si necesita que se comparen de manera diferente en otro lugar del programa.

Una tercera opción sería usar la clase sortedlist del módulo blist (descargo de responsabilidad: soy el autor). El constructor de sortedlist toma un parámetro key que le permite especificar una función para devolver la clave de clasificación de un elemento, similar al parámetro key de list.sort y sorted .

Answer 4

heapq ordena los objetos de la misma forma que list.sort , así que simplemente define un método __cmp__() dentro de la definición de tu clase, que se comparará con otra instancia de la misma clase:

def __cmp__(self, other):
    return cmp(self.intAttribute, other.intAttribute)

Funciona en Python 2.x.

En 3.x uso:

def __lt__(self, other):
    return self.intAttribute < other.intAttribute