Heapify y sift
Paso 1 de 14
Un array crudo, no un heap. Arreglarlo nunca toca todo el array: cada valor fuera de lugar recorre un solo camino.
La idea
Reparar un heap (montículo) nunca toca todo el array (arreglo). Un valor demasiado grande se hunde hacia las hojas, intercambiándose con su hijo menor; uno demasiado pequeño sube hacia la raíz. En ambos casos recorre un solo camino: como máximo log n intercambios.
Para construir un heap a partir de un montón sin orden, haz sift down empezando por el último padre y avanza hacia atrás. Eso cuesta O(n), porque la mayoría de los nodos ya están cerca del fondo.
Ejemplo del mundo real
El tanque de sedimentación de una planta potabilizadora hace esto sin que nadie lo revuelva. El limo pesado baja capa por capa hasta toparse con algo más pesado; la espuma sube hasta toparse con algo más ligero. Nada se compara con todo el tanque: cada partícula solo negocia con sus vecinos inmediatos.
El código
Te toca
Ordena los pasos.
- Intercámbialos y continúa desde la posición del hijo
- Empieza en el último padre, justo encima de la fila inferior
- Retrocede un índice a la izquierda y repite hasta terminar con el índice 0
- Compara el nodo con el menor de sus dos hijos
Mini quiz
1 / 3