Merge k Sorted Lists

Q: ¿Cuál es la complejidad temporal de Merge k Sorted Lists?

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 elementos. La memoria adicional es O(k) , aparte de la salida.

Q: ¿Por qué no juntar todos los valores y ordenarlos?

Eso es correcto y tarda O(N log N) . Ignora que las listas ya están ordenadas, así que paga log N por cada 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.

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 longitudes diferentes 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 aparezca varias veces, en una fila o en varias, aparecerá 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 distintas
Devuelveinteger-array: todos los valores de todas las filas, en una 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: Las filas empiezan con 2, 1 y 3, así que 1 va primero. Después, las cabezas son 2, 4 y 3, así que sigue 2, y así sucesivamente. La tercera fila se agota después de 5, dejando 6, 9 y 10.

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.

Para ir más allá

Encuentra el intervalo más pequeño [a, b] que contenga un valor de cada fila. ¿Puede un montículo de los primeros elementos de cada fila y el mayor de ellos hacerlo en O(N log k)?

Solución

Cada fila está ordenada, así que el valor no utilizado más pequeño siempre es el primer valor no utilizado de alguna fila, su cabeza. Examinar las k cabezas cuesta k pasos por cada uno de los N valores. Un montículo mínimo de las cabezas proporciona el menor en O(log k), lo que reduce el total de O(N·k) a O(N log k).

Compara todas las k cabezas para cada valor

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

Intuición

Mantén un índice pos[r] al principio de cada fila. En cada ronda se lee el elemento al principio de cada fila, se añade el menor y se avanza el índice de esa fila: el paso de combinación de merge sort, ampliado de dos listas a k. En el primer ejemplo, los elementos iniciales son 2, 1 y 3, así que sale el 1 y el elemento inicial de la segunda fila pasa a ser 4.

Cada uno de los N valores requiere una pasada por las k filas. Con 10^4 filas de un valor cada una, eso supone 10^8 comprobaciones de filas.

Algoritmo

Establece pos[r] = 0 para cada fila y cuenta los valores, N.
Repite N veces: examina cada fila cuya pos[r] todavía esté dentro de ella y recuerda la fila cuya cabecera sea la menor.
Añade esa cabecera al resultado y suma 1 a 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

Después de cada selección, solo cambia un elemento inicial, pero el recorrido vuelve a leer todos los k. Un montículo mínimo mantiene arriba el elemento inicial más pequeño. Etiqueta cada elemento inicial con su fila, para que después de extraer (value, row) sepas qué siguiente valor de la fila insertar. El montículo siempre contiene una entrada por cada fila a la que le queden valores, así que su elemento superior es el valor sin usar más pequeño.

En el primer ejemplo, el montículo empieza con 2, 1 y 3. Extrae 1, inserta 4. Extrae 2, inserta 6. Extrae 3, inserta 5. Extrae 4, inserta 10. Extrae 5: la tercera fila se ha agotado, así que no se inserta nada. Extrae 6, inserta 9, y después extrae 9 y 10.

Cada valor se inserta y se extrae una vez, y el montículo nunca contiene más de k entradas: 2N operaciones de O(log k). Con N = k = 10^4, eso supone menos de 3 × 10^5 pasos. El montículo ocupa O(k) de memoria.

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

Insertar solo los valores. Después de extraer un elemento, no puedes saber qué fila avanzar. Guarda la fila junto con el valor.
Usar por error un montículo máximo. C++ priority_queue y Rust BinaryHeap ponen el valor más grande arriba; usa greater<> o Reverse.
Insertar todos los valores al principio. El resultado sigue ordenado, pero el montículo crece hasta tener N elementos y el trabajo pasa a ser O(N log N).
Leer más allá del final de una fila corta. En el primer ejemplo, la tercera fila tiene dos valores, así que comprueba si hay un valor siguiente antes de insertarlo.
Descartar los duplicados. Los tres 5 del segundo ejemplo son valores distintos y todos deben estar en el resultado.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Merge k Sorted Lists?

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 elementos. La memoria adicional es O(k), aparte de la salida.

¿Por qué no juntar todos los valores y ordenarlos?

Eso es correcto y tarda O(N log N). Ignora que las listas ya están ordenadas, así que paga log N por cada 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.

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

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

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

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada

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