Merge k Sorted Lists

Q: ¿Cuál es la complejidad temporal de combinar k listas ordenadas?

Con un montículo mínimo, es O(N log k) , donde N es el número total de valores y k el número de listas. Cada valor se inserta y se extrae una vez, y el montículo contiene como máximo k entradas, por lo que cada operación cuesta O(log k) . La memoria adicional es O(k) , aparte de la salida.

Q: ¿Por qué no juntamos todos los valores y los ordenamos?

Eso es correcto y tarda O(N log N) , lo cual está bien para entradas pequeñas. Ignora que las listas ya están ordenadas, así que paga log N por valor, mientras que el montículo paga log k , y necesita tener todos los valores en memoria a la vez. El montículo también puede combinar listas que llegan como flujos, algo que la ordenación no puede hacer.

DifícilMontículo Lista enlazada

+10

Recibes k listas de enteros como filas de lists. Cada fila está ordenada en orden no decreciente, las filas pueden tener distintas longitudes y ninguna fila está vacía.

Combínalas en una sola lista que contenga todos los valores de todas las filas, ordenados en orden no decreciente, y devuélvela. Un valor que aparece varias veces, en una fila o en varias, aparece esa misma cantidad de veces en el resultado.

Función

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: las listas ordenadas, una por fila, de longitudes posiblemente diferentes
Devuelveinteger-array: todos los valores de cada fila, en una sola lista ordenada

Restricciones

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, y todas las filas juntas contienen como máximo 10⁴ valores
-10⁴ ≤ lists[i][j] ≤ 10⁴
Cada fila está ordenada en orden no decreciente.

Ejemplos

Entrada: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Salida: [1, 2, 3, 4, 5, 6, 9, 10]
Explicación: El valor más pequeño en general es 1, el primer valor de la segunda fila. Después, las filas empiezan con 2, 4 y 3, así que el siguiente es 2, y así sucesivamente. La tercera fila se acaba después de 5, por lo que quedan 6, 9 y 10 al final.

Entrada: lists = [[5], [-2, 5, 7], [0, 5]]
Salida: [-2, 0, 5, 5, 5, 7]
Explicación: Los tres 5 provienen de tres filas diferentes y los tres se conservan. El número negativo -2 se ordena antes que 0.

+14 pruebas ocultas al enviar

Para ir más allá

Encuentra el intervalo más pequeño [a, b] que contenga al menos un valor de cada fila. ¿Puede el mismo montículo de cabeceras de fila, junto con la cabecera más grande hasta el momento, encontrarlo en O(N log k)?

Solución

Cada fila está ordenada, así que el valor más pequeño que nadie ha usado todavía siempre es el primer valor sin usar de alguna fila. Todo el problema consiste en encontrar el menor de los k primeros valores de fila, N veces, donde N es la cantidad de valores. Recorrer todos los primeros valores cuesta k pasos por valor. Un montículo mínimo mantiene ordenados los primeros valores y proporciona el menor en O(log k), lo que reduce el total de O(N·k) a O(N log k). En la forma clásica, cada lista es una lista enlazada; aquí cada fila es un arreglo, y un índice por fila cumple la función del puntero al nodo.

Compara todos los k encabezados para cada valor

Correcto, pero no termina con las pruebas más grandes

Intuición

Mantén un índice por fila, pos[r], que apunte al primer valor de la fila r que aún no has usado: la cabeza de la fila. El menor valor sin usar de todos debe ser una de estas cabezas. Dentro de la fila r, cada valor sin usar está en la posición pos[r] o después, y la fila está ordenada, así que ninguno de ellos es menor que la cabeza.

Así que busca la cabeza menor examinando cada fila que aún tenga valores, añádela y avanza un paso el índice de esa fila. Repite hasta que hayan salido los N valores. Este es el paso de mezcla de merge sort, ampliado de dos listas a k.

En el primer ejemplo, las cabezas empiezan siendo 2, 1 y 3, así que sale primero 1 y la cabeza de la segunda fila pasa a ser 4. Después 2 (cabezas 2, 4, 3), luego 3 (cabezas 6, 4, 3), luego 4 y después 5, con lo que se vacía la tercera fila. En las últimas tres rondas solo se comparan 6 y 10, luego 9 y 10, y después solo 10.

El costo es de k comparaciones por cada uno de los N valores. Con 10^4 filas de un valor cada una, eso equivale a 10^8 comparaciones. C, Java o JavaScript las procesan en menos de un segundo, pero Python necesita más de diez segundos, y duplicar tanto N como k hace que todos los lenguajes sean cuatro veces más lentos. El desperdicio se ve en el registro: después de cada selección, solo ha cambiado una cabeza, pero en la siguiente ronda se vuelven a leer las k.

Algoritmo

Establece pos[r] = 0 para cada fila y cuenta los valores: N.
Repite N veces: revisa cada fila cuya pos[r] aún esté dentro de ella y recuerda la fila cuya cabecera sea la menor.
Añade esa cabecera al resultado y suma 1 a la pos de esa fila.
Devuelve el resultado.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

Montículo mínimo de las k cabezas

Intuición

El recorrido vuelve a leer las cabezas de k filas para encontrar la menor, aunque solo haya cambiado una cabeza desde la última ronda. Un montículo mínimo se crea precisamente para esto: contiene un conjunto de números con el menor en la cima, y tanto extraer el de la cima como añadir un número cuesta O(log size).

Coloca el primer valor de cada fila en el montículo, etiquetado con su número de fila. Luego repite: extrae el par más pequeño (value, row), añade value y, si esa fila tiene otro valor, insértalo con la misma etiqueta. El montículo siempre contiene exactamente una entrada por cada fila que todavía tiene valores: su cabeza; así, la cima es el menor valor sin usar de todos. Es la regla del recorrido, pero ejecutada más rápido.

Sigue el primer ejemplo con las filas numeradas desde 0. El montículo empieza con 2 (fila 0), 1 (fila 1) y 3 (fila 2). Extrae 1 e inserta el siguiente valor de la fila 1, 4. Extrae 2 e inserta 6 de la fila 0. Extrae 3 e inserta 5 de la fila 2. Extrae 4 e inserta 10. Extrae 5: la fila 2 se ha agotado, así que no se inserta nada y el montículo se reduce a 6 y 10. Extrae 6 e inserta 9. Extrae 9 y luego 10. El resultado es [1, 2, 3, 4, 5, 6, 9, 10].

Cada valor entra en el montículo una vez y sale una vez, y el montículo nunca contiene más de k entradas, así que cada una de esas 2N operaciones cuesta O(log k). Con N = k = 10^4, eso equivale a aproximadamente 2 × 10^4 × 14, menos de 3 × 10^5 pasos, frente a 10^8 para el recorrido. El montículo usa memoria O(k), nunca O(N), porque mantiene una cabeza por fila, no los valores que hay detrás.

Varias versiones construyen el montículo manualmente, en un arreglo de números de fila ordenados según la cabeza de cada fila, con los hijos de la posición i en 2i+1 y 2i+2 (en 2i y 2i+1 en Lua y R, que cuentan desde 1). También ahorra trabajo: después de extraer la cabeza de la fila que está en la cima, el siguiente valor de esa fila no es menor, así que la fila permanece en la cima y desciende una vez, en lugar de extraerla y luego insertarla.

Algoritmo

Inserta (lists[r][0], r) en un montículo mínimo ordenado por valor para cada fila r.
Mientras el montículo no esté vacío, extrae el par más pequeño (value, r) y añade value al resultado.
Si la fila r tiene un valor siguiente, insértalo junto con r.
Devuelve el resultado cuando el montículo esté vacío.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

Errores comunes y casos límite

La lógica del montón es breve. La mayoría de los errores se deben a qué se introduce en el montón y al orden en que se organiza.

Olvidar de dónde procede un valor. Si el montón contiene valores sin más, no puedes saber qué fila avanzar después de extraer uno. Guarda la fila junto con el valor.
Usar por error un montón máximo. C++ priority_queue y Rust BinaryHeap colocan el valor más grande en la cima; usa greater<> o Reverse. PriorityQueue de Java y heapq de Python ya devuelven el valor más pequeño.
Empates en heapq de Python. Cuando dos valores son iguales, la comparación de tuplas pasa al segundo elemento. Un número de fila se puede comparar sin problemas, pero un nodo de lista enlazada no, y la versión clásica falla con valores iguales. Coloca un número de fila o un contador en segundo lugar.
Introducir todos los valores al principio. Sigue ordenándolos correctamente, pero el montón crece hasta tener N elementos y el trabajo pasa a ser O(N log N). Mantén un primer elemento por fila.
Leer más allá del final de una fila corta. Las filas tienen longitudes distintas, así que comprueba que una fila tenga un valor siguiente antes de introducirlo.
Eliminar duplicados. Los valores iguales de filas distintas son valores separados, y todos deben incluirse en el resultado.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de combinar k listas ordenadas?

Con un montículo mínimo, es O(N log k), donde N es el número total de valores y k el número de listas. Cada valor se inserta y se extrae una vez, y el montículo contiene como máximo k entradas, por lo que cada operación cuesta O(log k). La memoria adicional es O(k), aparte de la salida.

¿Por qué no juntamos todos los valores y los ordenamos?

Eso es correcto y tarda O(N log N), lo cual está bien para entradas pequeñas. Ignora que las listas ya están ordenadas, así que paga log N por valor, mientras que el montículo paga log k, y necesita tener todos los valores en memoria a la vez. El montículo también puede combinar listas que llegan como flujos, algo que la ordenación no puede hacer.

¿Puedes combinar k listas ordenadas sin un montículo?

Sí, mediante divide y vencerás. Combina las listas por parejas con la combinación de dos listas, luego combina los resultados por parejas, y así sucesivamente. Hay log k rondas y cada ronda recorre cada valor una vez, por lo que también es O(N log k). Combinar las listas una tras otra en un resultado que va creciendo es más lento: los primeros valores se copian de nuevo en cada combinación, lo que suma O(N·k).

¿Por qué el heap solo necesita la cabeza de cada lista?

Cada lista está ordenada, por lo que su primer valor sin usar es el menor que le queda. Por lo tanto, el menor valor entre todas las listas es el menor de sus primeros elementos, y ningún valor más profundo de una lista puede ser menor. Cuando se extrae un primer elemento, el siguiente valor de la misma lista pasa a ser el primer elemento de esa lista y ocupa su lugar en el montículo.

Python

def mergeKLists(lists):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

Esperado

[1, 2, 3, 4, 5, 6, 9, 10]