¿Qué es el módulo heapq de Python?

Intenté “heapq” y llegué a la conclusión de que mis expectativas difieren de las que veo en la pantalla. Necesito a alguien que explique cómo funciona y dónde puede ser útil.

Del libro Módulo de la semana de Python, en el párrafo 2.2, Clasificación , está escrito

Si necesita mantener una lista ordenada a medida que agrega y elimina valores, revise heapq. Al utilizar las funciones de heapq para agregar o eliminar elementos de una lista, puede mantener el orden de la lista con una sobrecarga baja.

Esto es lo que hago y obtengo.

import heapq heap = [] for i in range(10): heap.append(i) heap [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] heapq.heapify(heap) heapq.heappush(heap, 10) heap [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] heapq.heappop(heap) 0 heap [1, 3, 2, 7, 4, 5, 6, 10, 8, 9] <<< Why the list does not remain sorted? heapq.heappushpop(heap, 11) 1 heap [2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6? 

Entonces, cuando vea que la lista de “montones” no está ordenada en absoluto, de hecho, cuanto más agregue y elimine los elementos, más desordenados se volverán. Los valores empujados toman posiciones inexplicables. Que esta pasando?

El módulo heapq mantiene el montón invariante , que no es lo mismo que mantener el objeto de lista real en orden ordenado.

Citando de la documentación de heapq :

Los montones son árboles binarios para los cuales cada nodo padre tiene un valor menor o igual que cualquiera de sus hijos. Esta implementación utiliza matrices para las que heap[k] <= heap[2*k+1] y heap[k] <= heap[2*k+2] para todo k , contando elementos desde cero. En aras de la comparación, los elementos no existentes se consideran infinitos. La propiedad interesante de un montón es que su elemento más pequeño es siempre la raíz, el heap[0] .

Esto significa que es muy eficiente encontrar el elemento más pequeño (solo tome el heap[0] ), lo que es ideal para una cola de prioridad. Después de eso, los siguientes 2 valores serán más grandes (o iguales) que el primero, y los siguientes 4 serán más grandes que su nodo "principal", luego los siguientes 8 serán más grandes, etc.

Puede leer más sobre la teoría detrás de la estructura de datos en la sección Teoría de la documentación . También puede ver esta conferencia del curso Introducción a los algoritmos de OpenCourseWare del MIT , que explica el algoritmo en términos generales.

Un montón se puede volver a convertir en una lista ordenada de manera muy eficiente:

 def heapsort(heap): return [heapq.heappop(heap) for _ in range(len(heap))] 

simplemente haciendo estallar el siguiente elemento del montón. Sin embargo, el uso de sorted(heap) debería ser aún más rápido, ya que el algoritmo TimSort utilizado por la clasificación de Python aprovechará el orden parcial ya presente en un montón.

Usaría un montón si solo está interesado en el valor más pequeño, o en los primeros n valores más pequeños, especialmente si está interesado en esos valores de forma continua; Agregar nuevos elementos y eliminar los más pequeños es realmente muy eficaz, más que reordenar la lista cada vez que agrega un valor.

¡Tu libro está mal! Como usted demuestra, un montón no es una lista ordenada (aunque una lista ordenada es un montón). ¿Qué es un montón? Para citar el manual de diseño de algoritmos de Skiena.

Los montones son una estructura de datos simple y elegante para admitir de manera eficiente las operaciones de cola de prioridad insertar y extraer-min. Funcionan manteniendo un orden parcial en el conjunto de elementos que es más débil que el ordenado (por lo que puede ser eficiente de mantener) pero más fuerte que el orden aleatorio (para que el elemento mínimo pueda identificarse rápidamente).

En comparación con una lista ordenada, un montón obedece a una condición más débil que el montón invariante . Antes de definirlo, primero piense por qué podría ser útil relajar la condición. La respuesta es que la condición más débil es más fácil de mantener . Puedes hacer menos con un montón, pero puedes hacerlo más rápido .

Un montón tiene tres operaciones:

  1. El mínimo de búsqueda es O (1)
  2. Insertar O (log n)
  3. Eliminar-Min O (log n)

Crucialmente Insertar es O (log n) que vence a O (n) para una lista ordenada.

¿Qué es el montón invariante? “Un árbol binario donde los padres dominan a sus hijos”. Es decir, ” p ≤ c para todos los niños c de p”. Skiena ilustra con imágenes y continúa demostrando el algoritmo para insertar elementos mientras mantiene el invariante. Si piensas un rato, puedes inventarlas tú mismo. (Pista: se les conoce como burbuja arriba y burbuja abajo)

La buena noticia es que Python, que incluye baterías, lo implementa todo en el módulo heapq . No define un tipo de stack (que creo que sería más fácil de usar), pero las proporciona como funciones auxiliares en la lista.

Moraleja: si escribe un algoritmo usando una lista ordenada pero solo inspecciona y elimina de un solo extremo, puede hacer que el algoritmo sea más eficiente usando un montón.

Para un problema en el que una estructura de datos de montón es útil, lea https://projecteuler.net/problem=500

Hay algunos malentendidos de la implementación de la estructura de datos del montón. El módulo heapq es en realidad una variante de la implementación del montón binario , donde los elementos del montón se almacenan en una lista, como se describe aquí: https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

Citando Wikipedia:

Los montones se implementan comúnmente con una matriz. Cualquier árbol binario se puede almacenar en una matriz, pero como un montón binario es siempre un árbol binario completo, se puede almacenar de forma compacta. No se requiere espacio para los punteros; en cambio, la matriz y los hijos de cada nodo se pueden encontrar mediante aritmética en los índices de matriz.

Esta imagen a continuación debería ayudarlo a sentir la diferencia entre el árbol y la representación de la lista del montón y ( tenga en cuenta que esto es un montón máximo, que es la inversa del min-montón habitual ):

introduzca la descripción de la imagen aquí

En general, la estructura de datos del montón es diferente de una lista ordenada en que sacrifica cierta información sobre si un elemento en particular es más grande o más pequeño que cualquier otro. Heap solo puede decir, que este elemento en particular es menos, que su padre y más grande, que sus hijos. Cuanta menos información almacena una estructura de datos, menos tiempo / memoria se tarda en modificarla. Compare la complejidad de algunas operaciones entre un montón y una matriz ordenada:

  Heap Sorted array Average Worst case Average Worst case Space O(n) O(n) O(n) O(n) Search O(n) O(n) O(log n) O(log n) Insert O(1) O(log n) O(n) O(n) Delete O(log n) O(log n) O(n) O(n)