> ## Documentation Index > Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt > Use this file to discover all available pages before exploring further. # Montículos (heaps) y colas de prioridad: inserción, extracción y heapsort > Montículos binarios explicados: propiedad de montículo de máximos y de mínimos, representación en un array, inserción con flotación, extracción con hundimiento, construcción en tiempo lineal, heapsort, colas de prioridad y sus usos en Dijkstra y planificación, con código y ejemplos resueltos. Una cola normal atiende por orden de llegada. Una **cola de prioridad** atiende siempre al elemento más importante: el paciente más grave en urgencias, el proceso con más prioridad en un sistema operativo o el nodo más cercano en el [algoritmo de Dijkstra](https://apuntes.simulab.es/programacion/algoritmos/dijkstra.md). La forma más eficiente de implementarla es el **montículo binario** (*heap*): un árbol que se guarda en un simple array y permite insertar y sacar el máximo en $O(\log n)$. ## Lo que vas a aprender * Qué es un montículo y la propiedad de montículo. * Cómo se guarda un árbol binario completo en un array. * La inserción (flotar) y la extracción (hundir). * Cómo construir un montículo en tiempo lineal. * El algoritmo de ordenación heapsort. * Las colas de prioridad y dónde se usan. ## Fundamentos teóricos ### Definición Un **montículo binario** es un árbol binario: 1. **Completo:** todos los niveles llenos salvo quizá el último, que se llena de izquierda a derecha. 2. Con la **propiedad de montículo**: en un montículo de **máximos**, cada nodo es mayor o igual que sus hijos (en uno de **mínimos**, menor o igual). Por tanto, la raíz es el máximo (o el mínimo). No está ordenado como un [árbol de búsqueda](https://apuntes.simulab.es/programacion/algoritmos/arboles-avl.md): entre hermanos no hay orden. ### Representación en un array Al ser completo, se guarda por niveles en un array sin punteros. Con índices desde 0: | Relación | Índice | | - | - | | Hijo izquierdo de $i$ | $2i + 1$ | | Hijo derecho de $i$ | $2i + 2$ | | Padre de $i$ | $\lfloor (i - 1)/2 \rfloor$ | Su altura es $\lfloor\log_2 n\rfloor$. ### Insertar: flotar Se pone el elemento al **final** del array y se va intercambiando con su padre mientras sea mayor que él. Coste $O(\log n)$. ### Extraer el máximo: hundir Se saca la raíz, se pone en su lugar el **último** elemento y se va intercambiando con el **mayor de sus hijos** mientras sea menor. Coste $O(\log n)$. ```python theme={null} def flotar(a, i): while i > 0 and a[(i - 1) // 2] < a[i]: p = (i - 1) // 2 a[i], a[p] = a[p], a[i] i = p def hundir(a, i, n): while True: mayor, izq, der = i, 2 * i + 1, 2 * i + 2 if izq < n and a[izq] > a[mayor]: mayor = izq if der < n and a[der] > a[mayor]: mayor = der if mayor == i: return a[i], a[mayor] = a[mayor], a[i] i = mayor def insertar(a, x): a.append(x) flotar(a, len(a) - 1) def extraer_max(a): maximo = a[0] a[0] = a[-1] a.pop() if a: hundir(a, 0, len(a)) return maximo ``` ### Construir un montículo: heapify Para convertir un array cualquiera en un montículo, se hunde cada nodo **desde el último padre hasta la raíz**: ```python theme={null} def construir(a): for i in range(len(a) // 2 - 1, -1, -1): hundir(a, i, len(a)) ``` Parece $O(n\log n)$, pero es $O(n)$: la mayoría de los nodos están abajo y se hunden muy poco. ### Heapsort 1. Construye un montículo de máximos: $O(n)$. 2. Intercambia la raíz (el máximo) con el último elemento, reduce el tamaño en 1 y hunde la nueva raíz. Repite: $O(n\log n)$. ```python theme={null} def heapsort(a): construir(a) for fin in range(len(a) - 1, 0, -1): a[0], a[fin] = a[fin], a[0] hundir(a, 0, fin) ``` Ordena **en el mismo array** (sin memoria extra) y en $O(n\log n)$ **siempre**, también en el peor caso. A cambio, no es estable y en la práctica suele ser algo más lento que quicksort. Puedes compararlo con otros en el simulador de [algoritmos de ordenación](https://apuntes.simulab.es/programacion/algoritmos/ordenacion.md). ### Colas de prioridad | Operación | Array desordenado | Array ordenado | Montículo binario | | - | - | - | - | | Insertar | $O(1)$ | $O(n)$ | $O(\log n)$ | | Ver el máximo | $O(n)$ | $O(1)$ | $O(1)$ | | Extraer el máximo | $O(n)$ | $O(1)$ | $O(\log n)$ | En Python, `heapq` implementa un montículo de **mínimos** sobre una lista; en Java, `PriorityQueue`; en C++, `std::priority_queue` (de máximos). **Usos:** Dijkstra y Prim, planificación de procesos en [sistemas operativos](https://apuntes.simulab.es/programacion/sistemas/sistemas-operativos.md), simulación de eventos, el algoritmo de Huffman de compresión, y obtener los $k$ mayores de un conjunto enorme sin ordenarlo entero. ## Ejemplos resueltos > [accordion] Ejemplo 1 · Insertar en un montículo de máximos > > Montículo `[50, 30, 40, 10, 20]`. Se inserta 45: queda en el índice 5, cuyo padre es el índice 2 (40). > > 45 > 40: se intercambian → `[50, 30, 45, 10, 20, 40]`. Padre del índice 2: el 0 (50). 45 \< 50: se para. > [accordion] Ejemplo 2 · Extraer el máximo > > De `[50, 30, 45, 10, 20, 40]` se saca el 50 y el 40 pasa a la raíz: `[40, 30, 45, 10, 20]`. > > Hijos de la raíz: 30 y 45. El mayor, 45, es mayor que 40: se intercambian → `[45, 30, 40, 10, 20]`. El 40 ya no tiene hijos: fin. > [accordion] Ejemplo 3 · Construir en tiempo lineal > > Array `[3, 9, 2, 1, 4, 5]`. Último padre: índice 2. > > * Índice 2 (2): hijo 5 → `[3, 9, 5, 1, 4, 2]`. > * Índice 1 (9): hijos 1 y 4, es mayor: no cambia. > * Índice 0 (3): hijos 9 y 5 → intercambia con 9: `[9, 3, 5, 1, 4, 2]`; el 3 tiene hijos 1 y 4 → con 4: `[9, 4, 5, 1, 3, 2]`. > > Resultado: `[9, 4, 5, 1, 3, 2]`. > [accordion] Ejemplo 4 · Los 3 mayores de un millón de datos > > Con un montículo de **mínimos** de tamaño 3: se recorre el millón de datos y, si un dato es mayor que la raíz (el menor de los 3 guardados), se sustituye. Coste $O(n\log k)$ en lugar de $O(n\log n)$ de ordenar todo. > > ```python theme={null} > import heapq > mayores = heapq.nlargest(3, datos) > ``` ## Errores frecuentes * **Pensar que un montículo está ordenado.** Solo está garantizado que la raíz es el máximo (o mínimo). * **Hundir intercambiando con cualquier hijo.** Hay que elegir el **mayor** (o el menor, en uno de mínimos). * **Equivocar los índices** según se empiece en 0 o en 1: con base 1, los hijos son $2i$ y $2i + 1$. * **Usar `heapq` como montículo de máximos.** Es de mínimos; para máximos, se guardan los valores cambiados de signo. * **Construir insertando uno a uno** ($O(n\log n)$) cuando ya se tiene el array: heapify es $O(n)$. ## Preguntas frecuentes > [accordion] ¿Qué tiene que ver con el 'heap' de la memoria? > > Nada, salvo el nombre. El *heap* de memoria (donde se reserva con `malloc` o `new`) es una zona de memoria dinámica; el montículo es una estructura de datos. Lo primero se explica en [memoria y punteros en C](https://apuntes.simulab.es/programacion/c/punteros.md). > [accordion] ¿Hay montículos más rápidos? > > Los montículos de Fibonacci bajan el coste de "disminuir clave" a $O(1)$ amortizado, lo que mejora Dijkstra en teoría a $O(E + V\log V)$. En la práctica, por sus constantes, el montículo binario suele ganar. ## Temas relacionados > [card] [Algoritmos de ordenación](https://apuntes.simulab.es/programacion/algoritmos/ordenacion.md) > > Heapsort frente a los demás. > [card] [Dijkstra y caminos mínimos](https://apuntes.simulab.es/programacion/algoritmos/dijkstra.md) > > El uso más famoso de una cola de prioridad. > [card] [Árboles AVL](https://apuntes.simulab.es/programacion/algoritmos/arboles-avl.md) > > Árboles de búsqueda equilibrados. This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.