İçeriğe geç

K-way merge

Ders 2 / 4 · 6 dk

K-way merge

Adım 1/17

Üç ş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

Heap herhangi bir anda kaç kayıt tutar?