Pular para o conteúdo

K-way merge

Aula 2 de 4 · 6 min

K-way merge

Passo 1 de 17

Três faixas, cada uma já ordenada. Só o valor na frente de uma faixa pode ser o próximo menor de todos.

A ideia

Só o primeiro valor de uma lista ordenada pode ser o próximo menor no geral. Então guarde só esses k primeiros em um min-heap.

Extraia o vencedor, adicione-o à saída e insira o valor que vinha logo atrás dele. O heap nunca passa de k, não importa o tamanho das listas.

Exemplo do mundo real

Um centro de triagem postal com k esteiras, cada uma já em ordem de data. Um funcionário só olha os k pacotes na frente das esteiras, pega o mais antigo, e a esteira de onde ele saiu avança um passo.

O código

Sua vez

O que isto imprime?

import heapq
heap = [(1, 0, 0), (2, 1, 0), (3, 2, 0)]   # the three heads
lists = [[1, 6], [2, 4], [3, 8]]
value, i, j = heapq.heappop(heap)
heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
print(value, heap[0][0])

Mini quiz

1 / 3

Quantas entradas o heap guarda a cada momento?