Qué es un montículo binario
Un montículo binario (en inglés heap) es un árbol binario casi completo: todos los niveles están llenos salvo el último, que se rellena de izquierda a derecha sin dejar huecos. Sobre esa forma impone una única regla, la propiedad de montículo:
- Montículo de máximos: todo padre es mayor o igual que sus dos hijos. El valor mayor de toda la colección está siempre en la raíz.
- Montículo de mínimos: todo padre es menor o igual que sus dos hijos. El valor menor está siempre en la raíz.
Como el árbol no tiene huecos, no hace falta guardar punteros: cabe entero en un arreglo, y las relaciones familiares se calculan con aritmética de índices. Es la razón de que sea tan rápido en la práctica, más allá de lo que diga la notación asintótica: los datos van seguidos en memoria.
padre(i) = ⌊(i − 1) / 2⌋
hijo_izquierdo(i) = 2i + 1
hijo_derecho(i) = 2i + 2
Arreglo: [ 50, 30, 40, 10, 20, 35 ]
Índices: 0 1 2 3 4 5
50 [0]
/ \
30 [1] 40 [2]
/ \ /
10 [3] 20 [4] 35 [5]La confusión más habitual: un montículo NO está ordenado
Quien viene de estudiar el árbol binario de búsqueda (BST) suele esperar que el recorrido en inorden de un montículo devuelva los valores ordenados. No es así. En el ejemplo de arriba, el inorden da 10, 30, 20, 50, 35, 40: ni ascendente ni descendente. El montículo solo ordena la relación vertical entre un padre y sus hijos; entre hermanos, o entre ramas distintas, no promete absolutamente nada.
Esa es la razón de que buscar un valor cualquiera en un montículo cueste O(n): no hay forma de descartar media estructura en cada paso, porque el 20 puede estar tanto a la izquierda como a la derecha. A cambio, el montículo sabe sin buscar dónde está el máximo (o el mínimo), y eso es justo lo que hace falta en una cola de prioridad.
| Característica | Montículo binario | Árbol binario de búsqueda (BST) |
|---|
| Qué ordena | Padre frente a sus hijos (orden vertical) | Izquierda menor, derecha mayor (orden total) |
| Recorrido en inorden | Sin ningún orden útil | Devuelve los valores ordenados |
| Encontrar el máximo o el mínimo | O(1): está en la raíz | O(log n): hay que bajar hasta el extremo |
| Buscar un valor cualquiera | O(n) | O(log n) si está equilibrado |
| Insertar | O(log n) | O(log n) equilibrado, O(n) degenerado |
| Forma del árbol | Siempre casi completo, equilibrado por construcción | Puede degenerar en una lista si no se rebalancea |
| Representación habitual | Arreglo, sin punteros | Nodos enlazados con punteros |
| Para qué se usa | Colas de prioridad, heapsort, top-k | Índices, búsquedas por rango, iteración ordenada |
Las cuatro operaciones, y lo que cuesta cada una
| Operación | Qué hace | Coste |
|---|
| Consultar la raíz | Leer el índice 0 sin tocar nada | O(1) |
| Insertar (sift-up) | Poner el valor al final y subirlo mientras sea prioritario frente a su padre | O(log n) |
| Extraer la raíz (sift-down) | Sacar el índice 0, subir el último elemento a la raíz y hundirlo | O(log n) |
| Construir (heapify de Floyd) | Hundir cada nodo desde el índice ⌊n/2⌋−1 hacia la raíz | O(n) |
| Buscar un valor | Recorrer todo: no hay atajo | O(n) |
| Heapsort | Construir y extraer n−1 veces al final del arreglo | O(n log n) |
El dato que más sorprende es el de la construcción. Insertar los n valores uno a uno cuesta O(n log n), pero el método de Floyd —el que reproduce el botón «Construir»— cuesta O(n): la mitad de los nodos son hojas y no bajan nada, un cuarto baja como mucho un nivel, un octavo como mucho dos… y la suma de esa serie converge a un múltiplo de n, no a n·log n. Es una de las demostraciones más elegantes de un primer curso de algoritmia.
Cómo se sigue una inserción, paso a paso
1
Coloca el valor en la primera posición libreEs el final del arreglo, índice n. Así el árbol sigue siendo casi completo, que es la condición que no se puede romper en ningún momento.
2
Compáralo con su padreEl padre está en ⌊(i−1)/2⌋. En un montículo de máximos, si el nuevo valor es mayor que su padre, la propiedad está rota justo ahí.
3
Intercámbialo y repiteSube al índice del padre y vuelve a comparar. Como el árbol tiene ⌊log₂ n⌋ + 1 niveles, no puede haber más de log n intercambios.
4
Para en cuanto el padre gane la comparaciónSi el padre ya es mayor (o menor, en un montículo de mínimos), no hace falta seguir: todos los de arriba también lo son, por transitividad. Es el error más común dejarlo subir hasta la raíz siempre.
5
La extracción es la misma jugada al revésSe saca la raíz, el último elemento ocupa su hueco y se hunde eligiendo en cada nivel al más prioritario de los dos hijos. Hundir hacia el hijo equivocado es el otro fallo clásico.
El heapsort, y por qué un montículo de máximos ordena de menor a mayor
El heapsort aprovecha que la raíz siempre es el valor extremo. Construye el montículo y después repite n−1 veces la misma jugada: intercambia la raíz con el último elemento del tramo activo, encoge ese tramo en uno —esa posición ya queda fija— y hunde la nueva raíz.
Con un montículo de máximos, cada vuelta deposita el mayor de los que quedan en la posición más a la derecha: el arreglo va quedando ascendente. Con uno de mínimos ocurre lo simétrico y queda descendente. Es contraintuitivo la primera vez, y es exactamente lo que se ve marcado en gris en el simulador cuando pulsas «Heapsort».
El heapsort ordena en O(n log n) también en el peor caso y sin memoria auxiliar, dos garantías que quicksort no da. Aun así, en la práctica suele perder frente a quicksort porque salta por el arreglo en lugar de recorrerlo seguido, y eso desaprovecha la caché del procesador. Tampoco es estable: dos valores iguales pueden acabar en orden intercambiado.
Dónde se usa de verdad
La cola de prioridad decide qué nodo se explora antes. Con un montículo binario, Dijkstra pasa de O(V²) a O((V+E)·log V), que es lo que hace viable calcular rutas sobre un mapa con millones de intersecciones.
Aquí interesa un montículo de mínimos: el siguiente nodo es el de menor distancia acumulada.
Qué proceso entra ahora en el procesador, y qué temporizador vence antes. El núcleo necesita responder «el más urgente» miles de veces por segundo, y consultarlo cuesta O(1).
Linux usa un árbol rojo-negro en su planificador CFS, pero los temporizadores del núcleo sí se apoyan en estructuras de tipo montículo.
Para quedarte con los 100 productos más vendidos de un flujo de millones de eventos, mantienes un montículo de mínimos de tamaño 100: si el nuevo evento supera a la raíz, sustituye a la raíz; si no, se descarta.
Coste O(n·log k) y memoria O(k), sin necesidad de ordenar los n elementos ni de guardarlos.
El algoritmo saca repetidamente los dos símbolos menos frecuentes para fusionarlos. Un montículo de mínimos entrega esos dos en O(log n) por vuelta y devuelve el nodo fusionado a la misma estructura.
Está detrás de formatos tan cotidianos como ZIP, JPEG o los antiguos MP3.
Colas de un supermercado, tráfico de red, líneas de producción: la simulación avanza sacando siempre el evento con la marca de tiempo menor de una cola de prioridad.
Insertar el evento que ese propio evento genera cuesta también O(log n), así que la simulación no se degrada al crecer.
Con un montículo de mínimos de tamaño k que guarda el primer elemento pendiente de cada lista, se fusionan k listas en O(N·log k). Es el corazón del mezclado externo cuando los datos no caben en memoria.
El mismo patrón aparece al unir resultados parciales de varios servidores en un buscador.
Preguntas frecuentes
¿Un montículo admite valores repetidos?
Sí, y sin ninguna precaución especial: la propiedad se enuncia con «mayor o igual» (o «menor o igual»), así que dos valores iguales pueden ser padre e hijo. Es una diferencia práctica frente al árbol binario de búsqueda, donde hay que decidir a qué lado van los duplicados y una decisión incoherente rompe las búsquedas.
Pruébalo cargando 7, 7, 3, 9, 3, 9, 1 en el campo de construcción.
¿Cómo se borra un elemento que no es la raíz?
Localizas su índice —eso ya cuesta O(n) si no lo tienes guardado—, lo sustituyes por el último elemento del arreglo, acortas el arreglo y desde esa posición aplicas una de las dos: si el valor nuevo es más prioritario que su padre, sube; si no, hunde. Las colas de prioridad serias mantienen un diccionario de valor a índice para evitar ese O(n).
¿Y cómo se cambia la prioridad de un elemento ya insertado?
Es la operación decrease-key que necesita Dijkstra. Modificas el valor en su índice y aplicas sift-up o sift-down según haya subido o bajado su prioridad: O(log n). Muchas implementaciones sencillas evitan esta operación insertando una entrada nueva y descartando las obsoletas al sacarlas, lo que a cambio hace crecer la cola.
¿Existen montículos que no sean binarios?
Sí. El montículo d-ario da d hijos a cada nodo: el árbol es más bajo, así que insertar es más rápido, pero hundir compara con d hijos en cada nivel. El montículo binomial y el de Fibonacci mejoran la fusión de dos colas y el decrease-key amortizado, a cambio de constantes altas que los hacen poco prácticos salvo en tamaños muy grandes.
Para la inmensa mayoría de los casos reales, el binario en arreglo sigue ganando por simplicidad y por localidad de memoria.
¿Hay montículos en las bibliotecas estándar?
Sí, y conviene conocer su sentido por defecto, porque no coinciden. En Python, heapq es de mínimos. En C++, priority_queue y las funciones make_heap/push_heap son de máximos. En Java, PriorityQueue es de mínimos según el orden natural. JavaScript no trae ninguno en su biblioteca estándar.
Truco clásico para invertir el sentido sin escribir un comparador: insertar los valores con el signo cambiado.
Recomendaciones al implementarlo
🧮Empieza el arreglo en el índice 0Muchos libros empiezan en 1 para que el padre sea ⌊i/2⌋ y quede más limpio. Mezclar las dos convenciones en el mismo código es una fuente inagotable de errores por uno.
🔽Hunde comparando con los dos hijosEl intercambio debe hacerse con el más prioritario de los dos, no con el primero que gane al padre. Elegir mal el hijo rompe la propiedad un nivel más abajo y el fallo tarda en aparecer.
📏Comprueba siempre el límite del tramoEn el heapsort, hundir usa el tamaño del tramo activo, no la longitud del arreglo. Usar la longitud completa vuelve a mezclar la parte ya ordenada y arruina el resultado.
🧪Prueba con el arreglo ya ordenado y con el invertidoSon los casos que destapan los errores de límites. Y con 0, 1 y 2 elementos: la mayoría de fallos de un montículo recién escrito están en esos tres tamaños.
✅Escribe un validador de la propiedadUna función que recorra los índices y compare cada padre con sus hijos ocupa cinco líneas y detecta al instante cualquier operación mal implementada. Es lo que hace el recuadro «Comprobación» de esta página.
⚖️Si necesitas orden total, no uses un montículoUn montículo solo responde bien a «dame el más prioritario». Si además necesitas recorrer los elementos en orden o buscar por rangos, la estructura adecuada es un árbol equilibrado.
- Esperar que el recorrido en inorden devuelva los valores ordenados: eso es del BST, no del montículo.
- Hundir intercambiando con el primer hijo que gane al padre, en vez de con el más prioritario de los dos.
- Olvidar comprobar que el hijo existe antes de compararlo, y leer fuera del arreglo en la última fila.
- Usar la longitud total del arreglo en lugar del tramo activo durante el heapsort.
- Construir insertando uno a uno cuando el heapify de Floyd resuelve lo mismo en O(n).
- Confundir el sentido de la biblioteca del lenguaje: heapq es de mínimos y priority_queue de C++ es de máximos.
- Dar por estable el heapsort: dos valores iguales pueden salir en orden distinto al de entrada.