Convertir una lista en heap in-place
La misión
Problema
Reorganiza una lista de números como un min-heap in-place (sin memoria extra), sin el módulo heapq, y devuélvela. En un min-heap guardado en una lista, los hijos del índice i están en 2i + 1 y 2i + 2, y cada padre es menor o igual que cada uno de sus hijos. Usa el método bottom-up (de abajo hacia arriba): haz sift down de cada padre, empezando por el último padre y avanzando hacia la raíz, para que toda la construcción tome O(n).
Ejemplos
Input: nums = [5, 3, 8, 1, 2]
Output: [1, 2, 8, 3, 5]
Por qué: 3 se intercambia con su hijo 1, y luego 5 baja desde la raíz pasando por debajo de 1 y 2
Input: nums = [9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: [1, 2, 3, 6, 5, 4, 7, 8, 9]
Input: nums = [42]
Output: [42]
Por qué: caso límite: un solo elemento ya es un heap
Pistas
0 / 3
Las hojas ya son heaps de tamaño uno, así que no hay nada que hacer en la segunda mitad de la lista. El último índice con un hijo es n // 2 - 1.
Sift down arregla un padre cuyos dos subárboles ya son heaps: intercámbialo con su hijo menor mientras ese hijo sea menor que él, y síguelo hacia abajo.
Llama a sift down para i desde n // 2 - 1 hasta 0. Ir hacia atrás garantiza que los dos subárboles de i ya se arreglaron antes que i.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Solución
El heapify bottom-up trata la lista como un árbol y la repara desde los padres más bajos hacia arriba. Sift down solo funciona cuando los dos subárboles de un nodo ya son heaps (montículos), y procesar los índices desde n // 2 - 1 hasta 0 lo garantiza, porque cada hijo tiene un índice mayor y se procesó antes. Cada sift down intercambia el nodo con su hijo menor hasta que ningún hijo sea menor, lo que restaura el orden de heap en ese subárbol. Hacer push de los valores uno por uno costaría O(n log n), pero aquí la mayoría de los nodos están cerca del fondo y solo pueden bajar uno o dos niveles: el trabajo total suma O(n). El espacio es O(1) porque todo ocurre dentro de la lista.
def sift_down(a, i, n):
while True:
smallest, left, right = i, 2 * i + 1, 2 * i + 2
if left < n and a[left] < a[smallest]:
smallest = left
if right < n and a[right] < a[smallest]:
smallest = right
if smallest == i: # both children are larger: done
return
a[i], a[smallest] = a[smallest], a[i]
i = smallest # follow the value down
def heapify(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # last parent back to the root
sift_down(a, i, n)
return a
print(heapify([5, 3, 8, 1, 2])) # -> [1, 2, 8, 3, 5]
print(heapify([9, 8, 7, 6, 5, 4, 3, 2, 1])) # -> [1, 2, 3, 6, 5, 4, 7, 8, 9]
print(heapify([42])) # -> [42]¿Lo que te frena es la idea y no el código? Heapify y sift lo explica.