درخت برنده (و بازنده) برای ادغام k-راهه

k فهرست مرتب را با یک درخت مسابقه ادغام می‌کند: ریشه کوچک‌ترین سر فهرست‌هاست و بعد از هر خروجی، فقط بازی‌های یک مسیر برگ تا ریشه دوباره انجام می‌شود؛ O(log k) برای هر عضو.

k فهرست مرتب داریم (مثلاً بخش‌های مرتب‌شده‌ی یک فایل بزرگ در مرتب‌سازی خارجی) و می‌خواهیم آن‌ها را در یک فهرست مرتب ادغام کنیم. هر بار باید کوچک‌ترین سر فهرست‌ها را پیدا کنیم؛ مقایسه‌ی همه O(k) است.

ادامه‌ی توضیح ↓

زمان: O(n log k) for n items in k runs
حافظه: O(k)
هوروویتز–ساهنی، فصل ۵

ورودی:

R 4×3خروجی PDF

چهار فهرست مرتب سه‌تایی؛ هر خروجی فقط دو بازی (log₂ ۴) را دوباره انجام می‌دهد و نتیجه ۱۲ عضو مرتب است.

class Node:
def __init__(self, key, run):
self.key = key
self.run = run # the run this key came from
self.left = None
self.right = None
self.parent = None
def k_way_merge(R):
# R: k sorted runs, one per row. The leaves are the runs' current heads; each inner node holds the smaller child.
k = len(R)
size = 1
while size < k:
size = size * 2
pos = [0] * size
leaves = []
for r in range(size):
key = float("inf")
if r < k and R[r]:
key = R[r][0]
leaves.append(Node(key, r))
level = leaves
while len(level) > 1:
up = []
for i in range(0, len(level), 2):
a = level[i]
b = level[i + 1]
w = a if a.key <= b.key else b
node = Node(w.key, w.run)
node.left = a
node.right = b
a.parent = node
b.parent = node
up.append(node)
level = up
root = level[0]
out = []
while root.key != float("inf"):
out.append(root.key)
r = root.run
pos[r] = pos[r] + 1
leaf = leaves[r]
leaf.key = R[r][pos[r]] if pos[r] < len(R[r]) else float("inf")
node = leaf.parent
while node is not None:
w = node.left if node.left.key <= node.right.key else node.right
node.key = w.key
node.run = w.run
node = node.parent
return out

ناوردا: هر گره‌ی داخلی کوچک‌ترین کلید برگ‌های زیرش را دارد؛ پس ریشه کوچک‌ترین عضو باقی‌مانده است.

شروع اجرا

∅

out—

متغیرهای محلی

نارنجی = در همین گام عوض شد

`R` list

[10, 15, 16][9, 20, 38][20, 20, 30][6, 15, 25]

Call stack

k_way_merge()خط 10

گام ۱ از ۳۳۳

توضیح

مسئله