ادغام k-راهه
k دنباله‌ی مرتب را با یک هیپ کمینه هم‌زمان ادغام می‌کند: هر بار کوچک‌ترینِ سرِ دنباله‌ها را برمی‌دارد. پایه‌ی مرتب‌سازی خارجی.
k دنباله‌ی مرتب داریم و می‌خواهیم یک دنباله‌ی مرتب بسازیم. کوچک‌ترین عضو کل، حتماً سرِ یکی از دنباله‌هاست. پس سرهای همه‌ی دنباله‌ها را در یک هیپ کمینه می‌گذاریم:
- زمان:
O(n log k) - حافظه:
O(n + k) - هوروویتز–ساهنی، فصل ۷
- CLRS، فصل ۶
سه دنباله‌ی مرتب پشت سر هم: (۳ ۹ ۱۴)، (۱ ۸ ۲۰ ۲۵) و (۵ ۶ ۱۲)؛ هیپ همیشه سه عضو دارد تا یکی تمام شود.
import heapqdef k_way_merge(a):# The sorted runs of a, found by scanning for descents.runs = []start = 0for i in range(1, len(a) + 1):if i == len(a) or a[i] < a[i - 1]:runs.append(a[start:i])start = i# A min-heap holds the front item of every run: (value, run, position).heap = [(run[0], r, 0) for r, run in enumerate(runs)]heapq.heapify(heap)out = []while heap:value, r, i = heapq.heappop(heap)out.append(value)if i + 1 < len(runs[r]):heapq.heappush(heap, (runs[r][i + 1], r, i + 1))return out
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
Call stack
- k_way_merge()خط 4
توضیح
ایده
k دنباله‌ی مرتب داریم و می‌خواهیم یک دنباله‌ی مرتب بسازیم. کوچک‌ترین عضو کل، حتماً سرِ یکی از دنباله‌هاست. پس سرهای همه‌ی دنباله‌ها را در یک هیپ کمینه می‌گذاریم:
- کوچک‌ترین را بردار و به خروجی اضافه کن.
- عضو بعدیِ همان دنباله را وارد هیپ کن.
هزینه
هر عضو یک بار وارد و یک بار خارج هیپ k عضوی می‌شود: O(n log k). بدون هیپ، پیدا کردن کوچک‌ترینِ k سر هر بار O(k) بود.
کاربرد
مرتب‌سازی خارجی: داده‌ای که در حافظه جا نمی‌شود را تکه‌تکه مرتب می‌کنند و روی دیسک می‌نویسند، بعد همه‌ی تکه‌ها را با ادغام k-راهه یکی می‌کنند. اینجا دنباله‌ها همان تکه‌های مرتبِ آرایه‌ی ورودی‌اند.
در trace به چه چیزی نگاه کنی
- هر سطر جدول یک دنباله است؛
outدر کارت بالا خروجی تا اینجاست وheapدر پنل حافظه.