# El montículo binario - Sitio: Ikusmira — enciclopedia en castellano de ciencias sociales y humanidades - URL canónica: https://ikusmira.org/p/el-monticulo-binario/ - Categoría: Informática - Publicado: 2025-11-15 - Autoría: Josemari Sarasola Ledesma — Editor coordinador; Profesor titular de escuela universitaria, Universidad del País Vasco/Euskal Herriko Unibertsitatea - Perfiles del autor: https://ekoizpen-zientifikoa.ehu.eus/investigadores/127490/detalle, https://dialnet.unirioja.es/servlet/autor?codigo=333202 - Política editorial (autoría, revisión, correcciones, financiación): https://ikusmira.org/politica-editorial/ El **montículo binario** (en inglés, *binary heap*) es una estructura de datos (*data structure*) que hace una sola cosa, y la hace deprisa: tener siempre a mano el elemento más pequeño de un conjunto que no deja de cambiar. Se pueden meter elementos en cualquier orden y sacar el mínimo en cualquier momento, y las dos operaciones cuestan un número de pasos proporcional al logaritmo del tamaño, unos veinte para un millón de elementos. Es lo que se necesita para una *cola de prioridad* (*priority queue*), en la que no sale el primero que llegó sino el más urgente, y por eso el montículo está dentro de los planificadores de los sistemas operativos, de los simuladores que procesan eventos por orden de hora, del [algoritmo de Dijkstra](https://ikusmira.org/p/el-algoritmo-de-dijkstra/) que calcula rutas y del árbol con que se construye la [codificación de Huffman](https://ikusmira.org/p/la-codificacion-de-huffman/). Su regla es más débil de lo que parece. Un montículo es un árbol binario en el que cada padre es menor o igual que sus dos hijos, y nada más: no dice nada sobre el orden entre hermanos ni entre primos. De esa regla se deduce que el mínimo está en la raíz, porque es menor que sus hijos, que son menores que los suyos, y así hasta abajo. Pero el resto del árbol puede estar bastante desordenado, y esa es la clave de su eficiencia. Un [árbol binario de búsqueda](https://ikusmira.org/p/el-arbol-binario-de-busqueda/) mantiene un orden total, a la izquierda lo menor y a la derecha lo mayor, y paga por ello; el montículo solo mantiene el orden a lo largo de cada camino de la raíz a una hoja, que es lo justo para saber dónde está el mínimo. La figura de esta página dibuja el mismo montículo dos veces. Arriba está el árbol, con la raíz en negro. Abajo está la memoria: una lista corriente en la que los nodos se guardan nivel a nivel, de izquierda a derecha. No hacen falta punteros, porque el árbol está siempre completo, todos los niveles llenos salvo el último, que se llena por la izquierda, y así la posición de cada nodo determina la de su familia: los hijos del elemento que ocupa la posición *i* están en 2*i* + 1 y 2*i* + 2, y su padre en la mitad de *i* − 1, redondeando hacia abajo. Moverse por el árbol es hacer esas cuentas, y un montículo de un millón de elementos ocupa exactamente un millón de casillas. Meter un elemento es ponerlo en la primera casilla libre, al final de la lista, que en el árbol es el primer hueco del último nivel. Probablemente eso rompe la regla, así que el nuevo se compara con su padre y, si es menor, se intercambian; y otra vez con el nuevo padre, y así hasta que encuentra uno menor o llega a la raíz. Se llama *flotar* o *subir*, y como el árbol completo de *n* elementos tiene log₂ *n* niveles, no puede costar más que ese número de intercambios. Sacar el mínimo es la operación simétrica: se retira la raíz, el último elemento de la lista ocupa su lugar y se *hunde*, cambiándose en cada nivel por el menor de sus dos hijos, hasta que los dos son mayores que él. La figura cuenta las comparaciones y los intercambios de cada operación, y con treinta y un elementos, cinco niveles, nunca pasan de unos pocos. Si se sacan todos los elementos uno tras otro, salen ordenados. Esa observación es de donde nació la estructura: J. W. J. Williams la publicó en 1964 en *Communications of the ACM*, con el nombre de *heap*, como pieza de un algoritmo de ordenación que llamó *heapsort*. El método mete todos los datos en el montículo y los saca de uno en uno, y como cada salida cuesta log₂ *n* pasos, el total es del orden de *n* log *n*, el mínimo posible para una ordenación por comparaciones. Tiene dos virtudes que los [algoritmos de ordenación](https://ikusmira.org/p/los-algoritmos-de-ordenacion/) más populares no reúnen a la vez: ese coste está garantizado incluso en el peor caso, y la ordenación se hace sobre la misma lista, sin memoria adicional, porque cada mínimo que sale deja libre la casilla del final donde se puede guardar. Robert Floyd mejoró el método unos meses después, en el mismo año y la misma revista. Su observación fue que no hace falta construir el montículo metiendo los elementos de uno en uno. Se pueden echar todos a la lista tal como vienen y después arreglar el árbol desde abajo, hundiendo cada padre empezando por el último que tiene hijos y terminando por la raíz. Parece la misma cantidad de trabajo, pero no lo es: la mitad de los nodos son hojas y no se hunden nada, una cuarta parte baja como mucho un nivel, una octava parte dos, y la suma de todo eso no pasa de *n*. Construir el montículo de Floyd cuesta un tiempo lineal garantizado, y la figura permite compararlo con el método ingenuo: con quince números al azar, Floyd hace unos ocho intercambios y las quince inserciones, unos once. Con datos al azar las dos maneras acaban siendo lineales en promedio; la diferencia está en el peor caso, cuando los datos llegan en orden inverso y cada nuevo elemento tiene que subir hasta la raíz, lo que devuelve las inserciones sucesivas al orden de *n* log *n*. Hay operaciones que el montículo no hace bien, y conviene saberlas. Buscar un elemento cualquiera exige recorrer la lista entera, porque la regla no dice en qué rama puede estar. Tampoco es barato ver el máximo de un montículo de mínimos, que puede ser cualquiera de las hojas. Algunos algoritmos necesitan además rebajar la prioridad de un elemento que ya está dentro, y Dijkstra lo hace cada vez que encuentra un camino más corto hacia un nodo; en un montículo binario eso cuesta log₂ *n* pasos si se sabe dónde está el elemento. Michael Fredman y Robert Tarjan presentaron en 1984 los montículos de Fibonacci, que rebajan una prioridad en tiempo constante en promedio y bajan el coste teórico de Dijkstra, aunque sus constantes son tan grandes que en la práctica los binarios suelen seguir ganando. El nombre invita a una confusión. En los lenguajes de programación también se llama montículo, o *heap*, a la zona de memoria donde se guardan los datos que el programa pide durante su ejecución, y las dos cosas no tienen nada que ver más allá de la palabra. El montículo de esta página es mucho más modesto y mucho más antiguo que casi todo lo que lo usa: una lista con una regla sobre los padres y los hijos, que Python ofrece en el módulo `heapq`, Java en `PriorityQueue` y C++ en `priority_queue`, casi sin cambios respecto a la de 1964. ## Fuentes - J. W. J. Williams — *Algorithm 232: Heapsort*, Communications of the ACM 7 (6) (1964) — https://doi.org/10.1145/512274.3734138 - Robert W. Floyd — *Algorithm 245: Treesort 3*, Communications of the ACM 7 (12) (1964) — https://doi.org/10.1145/355588.365103 - Michael L. Fredman y Robert Endre Tarjan — *Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms*, Journal of the ACM 34 (3) (1987) — https://doi.org/10.1145/28869.28874 --- Cómo citar: Sarasola, Josemari (2025). «El montículo binario». Ikusmira. https://ikusmira.org/p/el-monticulo-binario/ Índice del sitio para modelos: https://ikusmira.org/llms.txt