Introducción al módulo Python Heapq
Una introducción simple sobre cómo usar el módulo heapq de Python
Vijini Mallawaarachchi
6 de mayo de 2020·4 min de lectura
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.
8 estructuras de datos comunes que todo programador debe conocer
Las estructuras de datos son un medio especializado para organizar y almacenar datos en computadoras de tal manera que podamos realizar …
haciadatascience.com
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 El resultado de la impresión de elementos del montón será el siguiente. Tenga en cuenta que la palabra más corta 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 Observe cmo ha cambiado la comparacin de longitud en el Tenga en cuenta que ahora la palabra más larga 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! [1] heapq – Algoritmo de cola de montón – Documentación de Python 3.8.3rc1 (https://docs.python.org/3/library/heapq.html)__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")go come run write
go
está al frente del montón. Ahora puede probar otras funciones de heapq ajustando cadenas.Implementación de Max Heap usando Heapq
__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")__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
write
está al frente del montón.Pensamientos finales
Referencias