Saltar al contenido

Convertir una lista en heap in-place

Fácil#heapify#sift-down~15 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

¿Lo que te frena es la idea y no el código? Heapify y sift lo explica.

Python 3Ctrl+Enter ejecuta