Recorrido narrado · Subir, bajar y construir un heap

Construir en O(n)

Construir un heap con n valores insertándolos uno a uno cuesta O(n log n) en el peor caso. Hay una forma más rápida: poner todos los valores en el array tal cual, y bajar cada nodo, empezando por el último que tiene hijos y yendo hacia la raíz.

Texto

función construir(a):    para i desde longitud(a) / 2 − 1 hasta 0, bajando:        bajar(a, i)

Así se construye con el array [9, 7, 8, 5, 6, 2, 3], cuyas hojas son las posiciones 3 a 6:

Paso 1 de 4. El array tal cual. Las hojas son las posiciones 3 a 6. El último padre es la posición 2 (8), con hijos 2 y 3.

Paso 2 de 4. Bajar la posición 2: 8 se intercambia con su hijo menor, 2. 1 intercambio.

Paso 3 de 4. Bajar la posición 1: 7 tiene hijos 5 y 6 y se intercambia con 5. 1 intercambio.

Paso 4 de 4. Bajar la posición 0: 9 baja dos niveles, primero con 2 y luego con 3. 2 intercambios. En total, 4 intercambios para 7 valores.

Borde grueso: lo que se compara. Relleno con asterisco: lo que acaba de cambiar.

Las hojas (la mitad de los nodos) no se bajan. Los nodos de un nivel por encima de las hojas bajan como mucho 1; los de dos niveles, como mucho 2. Hay muchos nodos abajo, que bajan poco, y pocos arriba, que bajan mucho. Con 15 valores: 8 hojas no bajan; 4 nodos bajan como mucho 1 (4 intercambios), 2 como mucho 2 (4) y la raíz como mucho 3 (3). Son 11 intercambios como máximo, menos que 15. En general, la suma es menor que n: O(n).

Llegar a un heap válido por cualquier otro camino (por ejemplo, ordenando) no es seguir este algoritmo. La pregunta útil es por los pasos, no solo por el resultado.

Su fila en la tabla de costos

Con subir, bajar y construir, el heap completa su fila en la tabla de costos de la cola de prioridad:

Representación	`insertar`	`mínimo`	`extraer mínimo`	construir con n valores
heap binario	O(log n) peor caso	O(1)	O(log n) peor caso	O(n)
array ordenado	O(n)	O(1)	O(1), si el mínimo va al final	O(n log n)

Construir de golpe (O(n)) gana a insertar uno a uno (O(n log n)). El heap no es mejor en todo: la operación que no tiene es buscar una clave cualquiera, que sigue en O(n).