heapq - max heap python

¿Cuál es el módulo heapq de Python? (3)

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

Del libro Python Module of the Week bajo el párrafo 2.2 Sorting it is written

Si necesita mantener una lista ordenada a medida que agrega y elimina valores, consulte heapq. Al usar las funciones en heapq para agregar o eliminar elementos de una lista, puede mantener el orden de clasificación de la lista con un bajo costo.

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, como ve, la lista de "montones" no está ordenada del todo, de hecho, cuanto más agrega y quita los elementos, más desordenada se vuelve. Los valores empujados toman posiciones inexplicables. Que esta pasando?

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

Citando de la documentación de heapq :

Los montículos son árboles binarios para los cuales cada nodo padre tiene un valor menor o igual que cualquiera de sus hijos. Esta implementación usa matrices para las cuales heap[k] <= heap[2*k+1] y heap[k] <= heap[2*k+2] para todos los 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 siempre es la raíz, heap[0] .

Esto significa que es muy eficiente encontrar el elemento más pequeño (solo tomar el heap[0] ), 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 1er, y los siguientes 4 después de eso serán más grandes que su nodo "padre", 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 MIT OpenCourseWare Introduction to Algorithms , 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 sorted(heap) debería ser más rápido, ya que TimSort aprovechará el orden parcial ya presente en un montón.

Utilizarí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 manera continua; agregar nuevos elementos y eliminar los más pequeños es muy eficiente, más que recurrir a la lista cada vez que agregaste un valor.

Hay una mala comprensión de la implementación de la estructura de datos de 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 montículos 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 su lugar, el padre y los hijos de cada nodo se pueden encontrar mediante aritmética en índices de matriz.

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

En general, la estructura de datos del montón es diferente de una lista ordenada, ya 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 sus padres y más grande, que sus hijos. Cuanta menos información almacena una estructura de datos, menos tiempo / memoria se necesita para 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)

¡Tu libro está equivocado! Como lo 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 montículos son una estructura de datos simple y elegante para soportar eficientemente 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 orden ordenado (por lo que puede ser eficiente de mantener) pero más fuerte que el orden aleatorio (por lo que el elemento mínimo se puede identificar rápidamente).

Comparado 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é puede 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:

Encontrar-Mínimo es O (1)
Insertar O (log n)
Remove-Min O (log n)

Crucially Insert es O (log n) que supera O (n) para una lista ordenada.

¿Cuál 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 para demostrar el algoritmo para insertar elementos mientras mantiene el invariante. Si piensas un rato, puedes inventarlo tú mismo. (Sugerencia: se los conoce como burbujas hacia arriba y burbuja hacia abajo)

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

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

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