Fusionar k listas ordenadas
La misión
Problema
Recibes k listas, cada una ordenada de forma ascendente, y algunas pueden estar vacías. Combínalas en una sola lista ascendente que contenga todos los valores, duplicados incluidos. Lee cada lista solo desde el frente y no guardes más de un valor en espera por lista en ningún momento.
Ejemplos
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Input: lists = [[], [0], []]
Output: [0]
Por qué: las listas vacías simplemente no aportan nada
Input: lists = []
Output: []
Por qué: caso límite: no hay ninguna lista
Pistas
0 / 3
Volcar todo en una sola lista y ordenarla ignora que cada lista ya está en orden.
En cada momento, el siguiente valor de la salida tiene que ser el valor del frente de alguna de las listas. Solo necesitas el menor de esos k valores del frente.
Pon el valor del frente de cada lista no vacía en un min-heap, marcado con su lista y su posición. Haz pop del menor, agrégalo a la salida y haz push del siguiente valor de la misma lista, si lo hay. Detente cuando el heap quede vacío.
- Tiempo objetivo
- O(n log k)
- Espacio objetivo
- O(n)
Restricciones
- each of the k lists is sorted ascending
- some lists may be empty
Solución
El siguiente valor de la salida siempre es el menor de los valores del frente actuales, así que un min-heap con exactamente un valor del frente por lista lo entrega en O(log k). Cada entrada lleva el índice de su lista y su posición, así que después de un pop el heap (montículo) se rellena desde la lista que acaba de ceder un valor, lo que mantiene la regla de uno por lista. Marcar cada entrada con el índice de su lista también desempata valores iguales sin comparar nunca nada más. Con n valores en total, el tiempo es O(n log k) y el heap guarda como máximo k entradas.
import heapq
def merge_runs(lists):
heap = [(run[0], i, 0) for i, run in enumerate(lists) if run]
heapq.heapify(heap) # one front value per list
out = []
while heap:
value, i, j = heapq.heappop(heap)
out.append(value)
if j + 1 < len(lists[i]): # refill from the list just used
heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
return out
print(merge_runs([[1, 4, 5], [1, 3, 4], [2, 6]])) # -> [1, 1, 2, 3, 4, 4, 5, 6]
print(merge_runs([[], [0], []])) # -> [0]
print(merge_runs([])) # -> []¿Lo que te frena es la idea y no el código? K-way merge lo explica.