Merge k Sorted Lists

Q: Qual é a complexidade de tempo de Mesclar k listas ordenadas?

Com um min-heap, é 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, então cada operação custa O(log k) . 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 tempo O(N log N) , o que é adequado para entradas pequenas. Isso ignora o fato de 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, o que a ordenação não consegue fazer.

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 essa lista. 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, possivelmente de comprimentos diferentes
Retornainteger-array: todos os valores de todas as linhas, 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: O menor valor no geral é 1, o primeiro valor da segunda linha. Depois dele, as linhas começam com 2, 4 e 3, então 2 vem em seguida, e assim por diante. A terceira linha termina depois de 5, deixando 6, 9 e 10 no final.

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 valor negativo -2 vem antes de 0 na ordenação.

+14 testes ocultos ao enviar

Para ir além

Encontre o menor intervalo [a, b] que contenha pelo menos um valor de cada linha. O mesmo heap com os primeiros elementos de cada linha, mais o maior primeiro elemento encontrado até então, pode encontrá-lo em O(N log k)?

Solução

Cada linha está ordenada, então o menor valor que ninguém usou ainda é sempre o primeiro valor não usado de alguma linha. O problema inteiro consiste em encontrar o menor entre as k cabeças das linhas, N vezes, em que N é o número de valores. Percorrer todas as cabeças custa k etapas por valor. Um heap mínimo mantém as cabeças ordenadas e fornece o menor em O(log k), reduzindo o total de O(N·k) para O(N log k). Na forma clássica, cada lista é uma lista encadeada; aqui, cada linha é um array, e um índice por linha faz o papel do ponteiro para o nó.

Compare todos os k cabeçalhos para cada valor

Correta, mas não termina nos maiores testes

Intuição

Mantenha um índice por linha, pos[r], apontando para o primeiro valor da linha r que você ainda não usou: o início da linha. O menor valor ainda não usado de todos deve ser um desses inícios. Dentro da linha r, todo valor ainda não usado está em pos[r] ou depois dele, e a linha está ordenada, então nenhum deles é menor que o início.

Então, encontre o menor início examinando cada linha que ainda tenha valores, acrescente-o e avance o índice dessa linha uma posição. Repita até que todos os N valores tenham sido removidos. Essa é a etapa de intercalação do merge sort, ampliada de duas listas para k.

No primeiro exemplo, os inícios começam como 2, 1 e 3, então 1 sai primeiro e o início da segunda linha passa a ser 4. Depois, 2 (inícios 2, 4, 3), depois 3 (inícios 6, 4, 3), depois 4 e, em seguida, 5, que esvazia a terceira linha. Nas últimas três rodadas, comparam-se apenas 6 e 10, depois 9 e 10 e, por fim, somente 10.

O custo é de k comparações para cada um dos N valores. Com 10^4 linhas de um valor cada, isso representa 10^8 comparações. C, Java ou JavaScript dão conta delas em menos de um segundo, mas Python precisa de mais de dez segundos, e dobrar tanto N quanto k deixa cada linguagem quatro vezes mais lenta. O desperdício fica evidente no rastreamento: após cada escolha, apenas um início mudou, mas a rodada seguinte lê todos os k novamente.

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 elemento é o menor.
Adicione esse primeiro elemento ao resultado e incremente em 1 o 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

A varredura relê as k cabeças para encontrar a menor, embora apenas uma cabeça tenha mudado desde a última rodada. Um min-heap é feito exatamente para isso: ele mantém um conjunto de números com o menor no topo, e tanto remover o elemento do topo quanto adicionar um número custa O(log size).

Coloque o primeiro valor de cada linha no heap, cada um marcado com o número da linha. Então, repita: remova o menor par (value, row), acrescente value e, se essa linha tiver outro valor, insira-o com a mesma marcação. O heap sempre contém exatamente uma entrada para cada linha que ainda tem valores, sua cabeça, então o topo é o menor valor ainda não usado no conjunto todo. É a regra da varredura, executada mais rapidamente.

Acompanhe o primeiro exemplo com as linhas numeradas a partir de 0. O heap começa com 2 (linha 0), 1 (linha 1) e 3 (linha 2). Remova 1 e insira o próximo valor da linha 1, 4. Remova 2 e insira 6 da linha 0. Remova 3 e insira 5 da linha 2. Remova 4 e insira 10. Remova 5: os valores da linha 2 acabaram, então nada é inserido e o heap diminui para 6 e 10. Remova 6 e insira 9. Remova 9 e, em seguida, 10. O resultado é [1, 2, 3, 4, 5, 6, 9, 10].

Cada valor entra no heap uma vez e sai uma vez, e o heap nunca contém mais de k entradas, então cada uma dessas 2N operações custa O(log k). Com N = k = 10^4, isso dá cerca de 2 × 10^4 × 14, menos de 3 × 10^5 passos, contra 10^8 na varredura. O heap usa memória O(k), nunca O(N), porque mantém uma cabeça por linha, e não os valores que vêm depois dela.

Várias versões constroem o heap manualmente, em um array de números de linhas ordenados pela cabeça de cada linha, com os filhos do índice i nas posições 2i+1 e 2i+2 (em 2i e 2i+1 em Lua e R, que começam a contar em 1). Isso também economiza trabalho: depois de remover a cabeça da linha que está no topo, o próximo valor da linha não é menor, então a linha permanece no topo e desce uma vez, em vez de uma remoção seguida de uma inserção.

Algoritmo

Insira (lists[r][0], r) para cada linha r em uma min-heap ordenada pelo valor.
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

A lógica da heap é curta. A maioria dos erros vem do que é colocado na heap e da ordem usada.

Esquecer de onde veio um valor. Se a heap guardar apenas valores, você não poderá saber qual linha avançar após uma remoção. 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. PriorityQueue do Java e heapq do Python já retornam o menor elemento.
Empates em heapq do Python. Quando dois valores são iguais, a comparação da tupla passa para o segundo item. Um número de linha pode ser comparado sem problemas, mas um nó de lista encadeada não pode, e a versão clássica falha quando há valores iguais. Coloque um número de linha ou um contador na segunda posição.
Inserir todos os valores no início. Ainda assim, a ordenação será correta, mas a heap crescerá até N entradas e o trabalho passará a ser O(N log N). Mantenha a cabeça de cada linha.
Ler além do fim de uma linha curta. As linhas têm comprimentos diferentes, então verifique se uma linha tem um próximo valor antes de inseri-lo.
Descartar duplicatas. Valores iguais de linhas diferentes são valores distintos, e todos devem fazer parte do resultado.

Perguntas frequentes4

Qual é a complexidade de tempo de Mesclar k listas ordenadas?

Com um min-heap, é 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, então cada operação custa O(log k). 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 tempo O(N log N), o que é adequado para entradas pequenas. Isso ignora o fato de 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, o que a ordenação não consegue fazer.

Você consegue mesclar k listas ordenadas sem usar um heap?

Sim, usando dividir para conquistar. Mescle as listas em pares com a mesclagem de duas listas, depois mescle os resultados em pares, e assim por diante. Há log k rodadas, e cada rodada percorre todos os valores uma vez, então também é O(N log k). Mesclar as listas uma após a outra em um resultado crescente é mais lento: os valores iniciais são copiados novamente em cada mesclagem, o que resulta em O(N·k).

Por que o heap só precisa do início de cada lista?

Cada lista está ordenada, então seu primeiro valor não utilizado é o menor valor que ainda resta nela. Portanto, o menor valor entre todas as listas é o menor entre seus primeiros elementos, e nenhum valor mais abaixo em uma lista pode ser menor que ele. Quando um primeiro elemento sai, o próximo valor da mesma lista se torna o primeiro elemento dessa lista e ocupa seu lugar no heap.

Python

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

Casos de teste

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]