6.9. Colas de prioridad con montículos binarios¶
En las secciones anteriores usted aprendió sobre la estructura de datos LIFO denominada cola. Una variante importante de una cola se denomina una cola de prioridad. Una cola de prioridad actúa como una cola puesto que se quita un ítem eliminándolo del frente. Sin embargo, en una cola de prioridad el orden lógico de los ítems dentro de una cola se determina por su prioridad. Los ítems de prioridad más alta se encuentran en el frente de la cola y los elementos de menor prioridad se encuentran en el final. Por lo tanto, cuando se agrega un ítem en una cola de prioridad, el nuevo ítem puede moverse por todo el camino hasta el frente. Veremos que la cola de prioridad es una estructura de datos útil para algunos de los algoritmos de grafos que estudiaremos en el capítulo siguiente.
Usted probablemente puede pensar en un par de maneras fáciles de implementar una cola de prioridad usando funciones de ordenamiento y listas. Sin embargo, insertar en una lista es \(O(n)\) y ordenar una lista es \(O(n \log{n})\). Podemos hacerlo mejor. La manera clásica de implementar una cola de prioridad es usar una estructura de datos llamada montículo binario. Un montículo binario nos permitirá tanto agregar como hacer avanzar ítems en \(O(\log{n})\).
El montículo binario es interesante de estudiar porque cuando diagramamos el montículo se parece mucho a un árbol, pero cuando lo implementamos usamos únicamente una sola lista como representación interna. El montículo binario tiene dos variantes comunes: el montículo mín, en el que la clave más pequeña está siempre en el frente, y el montículo máx, en el que el valor clave más grande siempre está en el frente. En esta sección implementaremos el montículo mín. Dejamos como ejercicio la implementación del montículo máx.