A Montón es un caso especial de un árbol binario donde los nodos padres se comparan con sus hijos con sus valores y se organizan en consecuencia. Si se ha encontrado con mi artículo anterior titulado 8 estructuras de datos comunes, todo programador debe saber que hay dos tipos de montones; montón mínimo y montón máximo.

los heapq módulo de python implementa el heapag algoritmo de cola. Utiliza el min montón donde la clave del padre es menor o igual que la de sus hijos. En este artículo, presentaré el módulo python heapq y lo guiaré a través de algunos ejemplos de cómo usar heapq con tipos de datos primitivos y objetos con datos complejos.

Funciones de Heapq

Suponiendo que sabe cómo funciona la estructura de datos del montón, veamos qué funciones proporciona el modelo heapq de Python.

• heappush (montón, artículo) – Empuje el valor artículo en el montón
• heappop (montón) – Pop y devuelve el valor más pequeño de la montón
• heappushpop (montón, elemento) – Empuje el valor artículo en el montón y devolver el valor más pequeño de la montón
• acumular (x) – Convertir la lista X en un montón
• heapreplace (montón, artículo) – Pop y devuelve el valor más pequeño de la montón luego empuja el valor artículo en el montón

Ejemplo de tutorial de Heapq con tipos de datos primitivos

Veamos algunos ejemplos en los que usamos diferentes funciones de heapq. En primer lugar, debe importar el módulo heapq.

import heapq

Considere la lista de ejemplo a como se indica a continuación.

>>> a = [52, 94, 13, 77, 41]

Si apilamos esta lista, el resultado será el siguiente. Tenga en cuenta que la acumulación se realiza en el lugar.

>>> heapq.heapify(a)
>>> print(a)
[13, 41, 52, 77, 94]

Tenga en cuenta que el índice 0 contiene el valor más pequeño de todos los valores, que es 13.

Llevemos el valor 10 a nuestro montón.

>>> heapq.heappush(a,10)
>>> print(a)
[10, 41, 13, 77, 94, 52]

Tenga en cuenta que se suma 10 y, dado que 10 es el valor más pequeño de los valores disponibles, se encuentra en el índice 0.

Ahora salgamos de nuestro montón.

>>> print(heapq.heappop(a))
10
>>> print(a)
[13, 41, 52, 77, 94]

Cuando salimos de nuestro montón, eliminará el valor más pequeño del montón y lo devolverá. Ahora el valor 10 ya no está en nuestro montón.

Veamos cómo funcionan las funciones heappushpop (). Apliquemos el valor 28.

>>> print(heapq.heappushpop(a,28))
13
>>> print(a)
[28, 41, 52, 77, 94]

Puede ver que 28 se envía al montón y el valor más pequeño 13 se extrae del montón.

Ahora probemos la función heapreplace (). Reemplacemos el valor 3 en el montón.

>>> print(heapq.heapreplace(a,3))
28
>>> print(a)
[3, 41, 52, 77, 94]

Puede ver que aparece el valor 28 inicialmente más pequeño y luego se presiona nuestro nuevo valor 3. El índice 0 en el nuevo valor de montón 3. Note la diferencia en el orden de las acciones push y pop en las funciones heappushpop () y heapreplace ().

¿Cómo usar objetos en Heapq?

En el ejemplo anterior, he explicado cómo usar funciones heapq con tipos de datos primitivos como enteros. De manera similar, podemos usar objetos con funciones heapq para ordenar datos complejos como tuplas o incluso cadenas. Para esto, necesitamos tener una clase contenedora de acuerdo con nuestro escenario. Considere un caso en el que desee almacenar cadenas y ordénelas por la longitud de las cadenas, de la más corta a la más larga. Nuestra clase contenedora se verá de la siguiente manera.

class DataWrap:
    
    def __init__(self, data):
        self.data = data  
    
    def __lt__(self, other):
        return len(self.data) < len(other.data)

los __lt__ función (es la función de sobrecarga del operador para los operadores de comparación;>, ≥, ==,

# Create list of strings
my_strings = ["write", "go", "run", "come"]# Initialising
sorted_strings = []# Wrap strings and push to heap
for s in my_strings:
    heapObj = DataWrap(s)
    heapq.heappush(sorted_strings, heapObj)# Print the heap
for myObj in sorted_strings:
    print(myObj.data, end="t")

El resultado de la impresión de elementos del montón será el siguiente.

go	come	run	write

Tenga en cuenta que la palabra más corta go está al frente del montón. Ahora puede probar otras funciones de heapq ajustando cadenas.

Implementación de Max Heap usando Heapq

Podemos implementar fácilmente un montón máximo usando heapq. Todo lo que tienes que hacer es cambiar el operador de comparación en el __lt__ función para ordenar el valor más grande al frente. Probemos el ejemplo anterior con cadenas y sus longitudes.

class DataWrap:
    
    def __init__(self, data):
        self.data = data  
    
    def __lt__(self, other):
        return len(self.data) > len(other.data)# Create list of strings
my_strings = ["write", "go", "run", "come"]# Initialising
sorted_strings = []# Wrap strings and push to heap
for s in my_strings:
    heapObj = DataWrap(s)
    heapq.heappush(sorted_strings, heapObj)# Print the heap
for myObj in sorted_strings:
    print(myObj.data, end="t")

Observe cmo ha cambiado la comparacin de longitud en el __lt__ función de la DataWrap clase. El resultado de la impresión de elementos de este montón será el siguiente.

write	come	run	go

Tenga en cuenta que ahora la palabra más larga write está al frente del montón.

Pensamientos finales

Espero que haya encontrado este artículo informativo y útil durante las implementaciones con el módulo heapq. No dude en jugar con el código proporcionado.

¡Gracias por leer!

¡Salud!

Referencias

[1] heapq – Algoritmo de cola de montón – Documentación de Python 3.8.3rc1 (https://docs.python.org/3/library/heapq.html)