Montículo binario: una cola de prioridad en un vector

Un vector contiene quince claves y representa también un árbol: los hijos de la posición i están en 2i + 1 y 2i + 2. Construye el montículo insertando las claves una a una o empezando por el último padre. Sigue cada comparación e intercambio; después, extrae la clave menor y observa cómo la siguiente ocupa su lugar.

Ejemplo resuelto — Montículo binario: una cola de prioridad en un vector

Claves	15
Construcción por inserciones	34 comparaciones, 34 intercambios
Máximo de comparaciones por inserciones	34
Construcción desde el último padre	22 comparaciones, 11 intercambios
Máximo de comparaciones desde el último padre	22

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Montículo binario: una cola de prioridad en un vector

Un montículo binario de mínimos es un vector en el que la clave de cada posición i no supera a las claves de las posiciones 2i + 1 y 2i + 2, sus hijos; el padre de la posición i está en ⌊(i − 1) / 2⌋. Interpretado así, el vector representa un árbol binario completo, cuya clave menor siempre está en la posición 0, la raíz. Para insertar una clave, colócala al final y hazla ascender: intercámbiala con su padre mientras sea menor que él. Para extraer la menor, lleva la última clave a la raíz y hazla descender: intercámbiala con el menor de sus hijos mientras ese hijo sea menor que ella. Un montículo utilizado de esta forma es una cola de prioridad.

Qué significa cada símbolo

n: número de claves del montículo
i: posición en el vector, contando desde 0
h: altura de una posición: número de niveles que tiene debajo, ⌊log₂(n / (i + 1))⌋

Supone: Una comparación contrasta una clave con otra, y un intercambio permuta las claves de dos posiciones. Llevar la última clave a la raíz durante una extracción no cuenta como ninguna de esas operaciones. Una clave igual a su padre o al menor de sus hijos permanece donde está; si los dos hijos son iguales, se elige el izquierdo. El montículo mantiene la clave menor en la raíz. En un montículo de máximos se invierte el sentido de todas las comparaciones. Puedes usar hasta quince claves entre 0 y 99, para que el árbol entero quepa en la pantalla de un móvil. Los órdenes que se cuentan en la última fila corresponden a claves distintas.

Insertar una a una cuesta según la profundidad; construir desde el último padre, según la altura 🖖

Pulsa Descendente: inserción. Cada clave nueva es menor que todas las que ya están en el montículo, así que sube desde el último nivel hasta la raíz, con una comparación y un intercambio por nivel: 0 para la raíz, 1 para cada una de las dos siguientes, 2 para cada una de las cuatro siguientes y 3 para cada una de las ocho últimas. Suman 34. Pulsa ahora Descendente: desde abajo. Las mismas quince claves se colocan en orden de llegada y se reajusta por descenso cada posición que tiene hijos, desde la 6 hasta la 0. Una clave solo puede bajar tantos niveles como tenga debajo. Ocho de las quince posiciones son hojas: no tienen nada debajo. Esas posiciones, que en el primer método costaban tres niveles cada una, aquí no cuestan nada. Las alturas suman 11 y se hacen dos comparaciones por nivel: 22. En cualquier montículo, la suma de las alturas es n menos el número de dígitos 1 de su representación binaria; por eso, esta construcción siempre necesita menos de 2n comparaciones. Con 1.023 claves de mayor a menor, los dos métodos necesitan 8.194 y 2.026.

De menor a mayor, ambos métodos cuestan 14 comparaciones 🖖

Pulsa Ascendente: inserción. Ninguna clave nueva es menor que su padre: una comparación, ningún intercambio, 14 en total. Cambia a Desde el último padre y vuelven a ser 14, porque cada padre compara sus dos hijos, se compara con el menor y se detiene. El mínimo para ambos métodos es 14: toda clave salvo la raíz debe compararse al menos una vez. A partir de ahí, sus costes se separan. El orden de mayor a menor lleva la inserción una a una hasta su máximo; con las claves mezcladas, el coste suele quedar mucho más cerca del mínimo. En 200 mezclas de 1.000 claves, la inserción una a una necesitó una media de 2.235 comparaciones y la construcción desde abajo, 1.862, frente a las 7.987 de insertar las mismas claves de mayor a menor. Con quince claves, la diferencia es pequeña: pulsa Mezclar varias veces y verás que, de vez en cuando, gana la inserción una a una.

Un montículo está lejos de estar ordenado 🖖

Un montículo garantiza que ninguna clave supera a sus hijos. De los 5.040 órdenes posibles de siete claves distintas, 80 cumplen esa condición. La menor debe estar en la raíz; cualesquiera tres de las otras seis pueden formar el subárbol izquierdo, y cada subárbol debe ser también un montículo. El recuento se obtiene dividiendo 7! entre el producto de los tamaños de todos los subárboles, 7 · 3 · 3. Para quince claves, la tabla de resultados muestra 21.964.800 montículos entre 1.307.674.368.000 órdenes posibles, y solo uno está ordenado. Ese margen de libertad permite construir un montículo con poco trabajo. El orden aparece al extraer las claves una a una: pulsa Ordenar por montículos. Cada vez que extraes la raíz, la última clave ocupa su hueco y desciende hasta dejar la siguiente clave menor en la raíz. Las doce claves salen en orden: 3, 7, 12 y así hasta 93.

Problema resuelto al detalle

¿Cuántas comparaciones cuesta cada método con un millar de claves? 4 pasos
Pulsa Descendente: inserción y después Descendente: desde abajo, y explica de dónde salen 34 y 22. Considera ahora 1.023 claves que llegan de mayor a menor. ¿Cuántas comparaciones hace cada método?

Abre este problema en la herramienta
1. La posición i tiene profundidad ⌊log₂(i + 1)⌋: una posición a profundidad 0, dos a profundidad 1, cuatro a profundidad 2 y ocho a profundidad 3. Si llegan de mayor a menor, cada clave nueva es la menor hasta ese momento y asciende hasta la raíz, con una comparación y un intercambio por nivel: 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34.
  
  $0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34$
2. Al construir desde el último padre, lo que cuenta es la altura: 3 para la raíz, 2 para las posiciones 1 y 2, 1 para las cuatro posiciones de profundidad 2 y 0 para las ocho hojas. La suma es 11. Con las claves de mayor a menor, cada una desciende todo lo posible. Como con quince claves todos los padres tienen dos hijos, cada nivel cuesta dos comparaciones: 22 comparaciones y 11 intercambios.
  
  $3 + 2 \cdot 2 + 4 \cdot 1 = 11, 2 \times 11 = 22$
3. 1.023 = 2¹⁰ − 1 corresponde a un árbol binario perfecto de diez niveles, con 2ᵈ posiciones a profundidad d. La inserción una a una cuesta la suma de las profundidades: 1 · 2 + 2 · 4 + 3 · 8 + ⋯ + 9 · 512 = 8.194 comparaciones y otros tantos intercambios.
  
  $d = 0 \sum 9 d \cdot 2^{d} = 8 \cdot 2^{10} + 2 = 8194$
4. La construcción desde el último padre cuesta el doble de la suma de las alturas. Hay 2⁹ posiciones de altura 0, 2⁸ de altura 1, y así sucesivamente hasta la raíz, de altura 9: 1 · 256 + 2 · 128 + ⋯ + 9 · 1 = 1.013, que es 1.023 menos los diez dígitos 1 de su representación binaria. El doble da 2.026 comparaciones, con 1.013 intercambios.
  
  $h = 0 \sum 9 h \cdot 2^{9 - h} = 1023 - 10 = 1013, 2 \times 1013 = 2026$
Respuesta

8.194 comparaciones al insertar una a una y 2.026 al construir desde el último padre: unas ocho por clave frente a dos. La mayoría de las posiciones de un montículo tienen mucha profundidad y poca altura. El coste de insertar depende de la profundidad; el de construir desde el último padre, de la altura. La herramienta admite hasta quince claves, para las que este mismo cálculo da las 34 y 22 comparaciones que muestra.

$8194 against 2026$

Ruta de aprendizaje

Qué operaciones abarata una estructura de datos

Referencias (2)

Heapsort as first published: J. W. J. Williams, "Algorithm 232: Heapsort," Communications of the ACM 7(6), 347–348, June 1964.
The heap-based sort published six months later, close to the version used today: Robert W. Floyd, "Algorithm 245: Treesort 3," Communications of the ACM 7(12), 701, December 1964.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.