K-way merge
Passo 1 de 17
no heap0
saída
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