K-way merge
Paso 1 de 17
Tres carriles, cada uno ya ordenado. Solo el valor al frente de un carril puede ser el siguiente menor de todos.
La idea
Solo el valor del frente de una lista ordenada puede ser el siguiente más pequeño de todos. Así que guarda solo esas k cabezas en un min-heap.
Haz pop del ganador, agrégalo a la salida y haz push del valor que le seguía en su lista. El heap (montículo) nunca pasa de k, sin importar qué tan largas sean las listas.
Ejemplo del mundo real
Una sala de distribución postal con k cintas transportadoras, cada una ya ordenada por fecha. Un empleado solo mira los k paquetes del frente de las cintas, toma el más antiguo, y la cinta de la que lo sacó avanza un paso.
El código
Te toca
¿Qué imprime esto?
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