Merge k Sorted Lists

Q: Qual é a complexidade de tempo de Merge k Sorted Lists?

Com um min-heap, a complexidade é O(N log k) , em que N é o número total de valores e k é o número de listas. Cada valor é inserido e removido uma vez, e o heap contém no máximo k entradas. A memória extra é O(k) , além da saída.

Q: Por que não colocar todos os valores juntos e ordená-los?

Isso está correto e leva O(N log N) de tempo. Isso ignora que as listas já estão ordenadas, então paga log N por valor, enquanto o heap paga log k , e precisa manter todos os valores na memória ao mesmo tempo. O heap também pode mesclar listas que chegam como fluxos.

DifícilHeap Lista ligada

+10

Você recebe k listas de números inteiros como linhas de lists. Cada linha está ordenada em ordem não decrescente, as linhas podem ter comprimentos diferentes e nenhuma linha está vazia.

Mescle-as em uma única lista que contenha todos os valores de todas as linhas, ordenados em ordem não decrescente, e retorne-a. Um valor que aparece várias vezes, em uma linha ou em várias, aparece essa mesma quantidade de vezes no resultado.

Função

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

listsinteger-2d-array: as listas ordenadas, uma por linha, de comprimentos possivelmente diferentes
Retornainteger-array: todos os valores de cada linha, em uma única lista ordenada

Restrições

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, e todas as linhas juntas contêm no máximo 10⁴ valores
-10⁴ ≤ lists[i][j] ≤ 10⁴
Cada linha está ordenada em ordem não decrescente.

Exemplos

Entrada: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Saída: [1, 2, 3, 4, 5, 6, 9, 10]
Explicação: As linhas começam com 2, 1 e 3, então 1 vem primeiro. As cabeças são então 2, 4 e 3, então 2 vem em seguida, e assim por diante. A terceira linha acaba depois de 5, restando 6, 9 e 10.

Entrada: lists = [[5], [-2, 5, 7], [0, 5]]
Saída: [-2, 0, 5, 5, 5, 7]
Explicação: Os três 5 vêm de três linhas diferentes e os três permanecem. O número negativo -2 é ordenado antes de 0.

Para ir além

Encontre o menor intervalo [a, b] que contenha um valor de cada linha. Um heap com os primeiros elementos das linhas e o maior primeiro elemento consegue fazer isso em O(N log k)?

Solução

Cada linha está ordenada, então o menor valor não utilizado é sempre o primeiro valor não utilizado de alguma linha, seu início. Percorrer todos os k inícios custa k etapas para cada um dos N valores. Um min-heap dos inícios fornece o menor em O(log k), o que reduz o total de O(N·k) para O(N log k).

Compare todos os k cabeçalhos para cada valor

Correta, mas não termina nos maiores testes

Intuição

Mantenha um índice pos[r] no início de cada linha. A cada rodada, leia todos os elementos no início, acrescente o menor e avance o índice dessa linha: a etapa de intercalação do merge sort, ampliada de duas listas para k. No primeiro exemplo, os elementos no início são 2, 1 e 3, então 1 é acrescentado e o elemento no início da segunda linha passa a ser 4.

Cada um dos N valores exige uma passagem por todas as k linhas. Com 10^4 linhas com um valor cada, isso resulta em 10^8 verificações de linha.

Algoritmo

Defina pos[r] = 0 para cada linha e conte os valores, N.
Repita N vezes: examine cada linha com pos[r] ainda dentro dela e memorize a linha cujo primeiro valor é o menor.
Acrescente esse primeiro valor ao resultado e some 1 a pos dessa linha.
Retorne o 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

Min-heap das k cabeças

Intuição

Após cada seleção, apenas uma cabeça muda, mas a varredura relê todos os k. Um min-heap mantém a menor das cabeças no topo. Marque cada cabeça com sua linha, assim, depois de remover (value, row), você sabe qual é o próximo valor daquela linha a inserir. O heap sempre contém uma entrada por linha que ainda tem valores, então seu topo é o menor valor ainda não utilizado.

No primeiro exemplo, o heap começa com 2, 1 e 3. Remova 1, insira 4. Remova 2, insira 6. Remova 3, insira 5. Remova 4, insira 10. Remova 5: a terceira linha foi esgotada, então nada é inserido. Remova 6, insira 9, depois remova 9 e 10.

Cada valor entra e sai uma vez, e o heap nunca contém mais de k entradas: 2N operações de O(log k). Com N = k = 10^4, isso representa menos de 3 × 10^5 etapas. O heap usa memória O(k).

Algoritmo

Insira (lists[r][0], r) em uma min-heap ordenada por valor para cada linha r.
Enquanto a heap não estiver vazia, remova o menor par (value, r) e acrescente value ao resultado.
Se a linha r tiver um próximo valor, insira-o junto com r.
Retorne o resultado quando a heap estiver vazia.

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

Armadilhas e casos extremos

Inserir apenas os valores. Depois de remover um elemento, você não consegue saber qual linha avançar. Armazene a linha junto com o valor.
Usar uma max-heap por engano. C++ priority_queue e Rust BinaryHeap colocam o maior elemento no topo; use greater<> ou Reverse.
Inserir todos os valores no início. O resultado ainda fica ordenado, mas a heap cresce até N elementos e o trabalho passa a ser O(N log N).
Ler além do fim de uma linha curta. No primeiro exemplo, a terceira linha tem dois valores, então verifique se há um próximo valor antes de inseri-lo.
Descartar duplicatas. Os três valores 5 do segundo exemplo são valores separados, e todos devem fazer parte do resultado.

Perguntas frequentes3

Qual é a complexidade de tempo de Merge k Sorted Lists?

Com um min-heap, a complexidade é O(N log k), em que N é o número total de valores e k é o número de listas. Cada valor é inserido e removido uma vez, e o heap contém no máximo k entradas. A memória extra é O(k), além da saída.

Por que não colocar todos os valores juntos e ordená-los?

Isso está correto e leva O(N log N) de tempo. Isso ignora que as listas já estão ordenadas, então paga log N por valor, enquanto o heap paga log k, e precisa manter todos os valores na memória ao mesmo tempo. O heap também pode mesclar listas que chegam como fluxos.

Você consegue mesclar k listas ordenadas sem um heap?

Sim, usando divisão e conquista. Mescle as listas em pares com a mesclagem de duas listas, depois mescle os resultados em pares, e assim por diante: log k rodadas que percorrem cada valor uma vez, resultando em O(N log k). Mesclar as listas uma após a outra em um resultado crescente é mais lento, O(N·k), porque os valores iniciais são copiados novamente em cada mesclagem.

def mergeKLists(lists):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

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