K-way merge
Adım 1/17
heap'te0
çıktı
Üç şerit, her biri zaten sıralı. Genel olarak sıradaki en küçük ancak bir şeridin başındaki değer olabilir.
Fikir
Tüm listeler arasında bir sonraki en küçük değer ancak bir listenin başındaki olabilir. O halde yalnız bu k başı bir min-heap'te tut.
Kazananı pop et, çıktıya ekle ve onun arkasından öne çıkan değeri push et. Listeler ne kadar uzun olursa olsun heap asla k'yı geçmez.
Gerçek hayattan örnek
k konveyör bandı olan bir posta ayırma salonu düşün; her bant zaten tarih sırasında. Görevli yalnız bantların önündeki k pakete bakar, en eskisini alır ve onun arkasındaki bant bir adım ilerler.
Kod
Sıra sende
Bu kod ne yazdırır?
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