Python Heaps-ters

La documentación de Python del módulo heaqp nos da el ejemplo de que pueden usarse para implementar colas de prioridad. Más allá de eso encontramos escasa información acerca de sus aplicaciones prácticas y —quizá— demasiados detalles acerca de invariantes y la teoría detrás de esa estructura de datos llamada heap. Es fácil echar un vistazo superficial y encogerse de hombros, sin haber entendido mucho y con la sensación de que éste no es un módulo que vayamos a necesitar algún día.

Pero no es así. Las heaps importan, y mucho: del mismo modo que es razonable afirmar que las tablas hash (conocidas en Python como diccionarios) son la estructura de datos más importante conocida por la humanidad, la heap se encuentra fácilmente entre las tres más importantes. Nos permiten acceder en todo momento al mayor (o menor) elemento en tiempo constante, O(1), mientras que insertar elementos ocurre en tiempo logarítmico, O(log n). Las ramificaciones de estas propiedades son inmensas, y —sin ir más lejos— es lo que subyace en el algoritmo de ordenación heapsort.

Problemas que de otra forma serían intratables (ejemplo: “¿cuáles son los n menores elementos de este fichero con diez billones de enteros?”) tienen una solución elegante y de apenas unas líneas de código cuando podemos usar una heap. En esta charla vamos a incorporar esta estructura de datos a nuestro arsenal, entender cómo funciona y aprender a reconocer cuándo es la herramienta adecuada para enfrentarnos a nuestro problema.

Resumen esquemático de la charla:

Qué es una heap:
- Inserción: O(log n)
- Consultar la raíz: O(1)
- Borrado: O(log n)
Por qué importan y qué problema resuelven.
Aplicaciones de una heap:
- Los n menores elementos de un conjunto.
- Heapsort.
- Medianas.
Reconocer cuándo hemos de usar una heap.
Dos opciones para la implementación:
- Árbol binario.
- Vector.
Heaps en Python: el módulo heapq.
Idea: encapsularlo en nuestra propia clase.