ادغامِ k جریانِ مرتب، کوچک‌ترین سرِ آماده را بیرون می‌دهد و همان منبع را جلو می‌برد. heap ورودیِ نامرتب را خودکار مرتب نمی‌کند. این تمرینِ محدود هم مصرفِ تنبلِ تولیدکننده‌ها را نشان می‌دهد و هم وارونگیِ دیررس را؛ اعتبارسنجیِ هنگامِ خواندن ممکن است پس از خروجِ بخشی از نتیجه خطا بدهد.
کلیدِ کامل را یکسان کنیم
سه منبع داریم: [(۱،A)،(۴،D)]،[(۲،B)،(۴،C)] و[(۰،E)،(۷،F)]. کلیدِ ترتیب زوجِ امتیاز و شناسه است؛ در امتیازِ برابر، C پیش ازDمی‌آید. همهٔ شناسه‌ها یکتا و امتیازها صحیح‌اند. فقط مرتب‌بودن بر امتیاز، قراردادِ کاملِ تساوی را در هر کاربرد تضمین نمی‌کند.
در آغاز از هر منبعِ غیرخالی یک سر می‌خوانیم. heap سرها را با همان کلید نگه می‌دارد. هر بار یک سر برداشته، yield می‌شود و در ادامه، تنها منبعِ همان سر یک گام جلو می‌رود. بافرکردنِ همهٔ رکوردها برای تولیدِ اولین نتیجه لازم نیست.
مصرفِ سه خروجی را واقعاً بشماریم
سه خروجیِ نخست۰E،۱Aو۲Bهستند. در نقطهٔ توقفِ generator پس از سومین yield، شمارِ خواندنِ سه منبع[۲،۱،۲] است. زمانِ بازگشت از yield مهم است: سرِ بعدیِ منبعِ سومین خروجی هنوز در مرحلهٔ بعد خوانده می‌شود؛ عددِ مصرف را بدونِ قراردادِ توقف تفسیر نکنید.
با ادامهٔ همان iterator، ترتیبِ کامل۰E،۱A،۲B،۴C،۴Dو۷Fساخته می‌شود. oracleِ اول همهٔ ورودی‌ها را یک‌جا با کلیدِ کامل مرتب می‌کند؛ oracleِ دوم heapq.merge استاندارد را روی منابعِ معتبر اجرا می‌کند. چندمجموعهٔ شناسه‌ها و تمام ترتیب با هر دو برابرند.
تعویضِ ترتیبِ منابع نتیجه را عوض نکند
هر شش جایگشتِ سه منبع اجرا شده‌اند. چون شناسه بخشی از کلیدِ کامل است، نتیجهٔ نهایی در این داده یکسان می‌ماند. اگر تساوی را به ترتیبِ ورودِ منبع بسپاریم، این شرطِ مستقل دیگر برقرار نیست؛ قاعدهٔ تساوی باید پیش از مقایسه معلوم باشد.
حداکثر یک سر برای هر منبع در heap نگه می‌داریم، ولی فهرست‌های ورودی و JSON کاملِ نتیجه در همین تمرین حافظه دارند. از شکلِ الگوریتم، benchmarkِ دیسک، شبکه یا حافظهٔ ثابتِ کلِ برنامه نتیجه نمی‌گیریم. همهٔ منابعِ این فایل محدود و حافظه‌ای‌اند.
یک وارونگیِ دیررس را پنهان نکنیم
منبعِ اول را عمداً [(۴،D)،(۱،A)] می‌گذاریم. با guard خاموش، خروجی۰E،۲B،۴C،۴D،۱A،۷Fمی‌شود؛۱Aدیرتر از۴Dآمده و ترتیب شکسته است. heap چیزی را که هنوز از منبع خوانده نشده نمی‌بیند.
با guard روشن، هنگامِ خواندنِ ۱Aبعد از۴Dخطا می‌گیریم، اما پیشوندِ ۰E،۲B،۴C،۴Dپیش‌تر تحویل شده است. پس این محافظ «همه یا هیچ» نیست و خروجیِ قبلی را پس نمی‌گیرد. مقصدِ دارای اثرِ واقعی به طراحیِ جداگانهٔ اعتبارسنجی و ثبت نیاز دارد.
مرزِ این ابزار با ادامه و top-k
نقطهٔ ادامهٔ سند ثبتِ پایدار و پاسخِ دیررس را بررسی می‌کند؛ اینجا هم‌زمانی یا ذخیره‌ساز نداریم. top-k فقط زیرمجموعهٔ برتر می‌خواهد؛ ادغامِ حاضر تمامِ دنباله را به ترتیب می‌دهد.
چهار ورودیِ منفی برای نوعِ کلید، شناسهٔ تکراری و سقفِ منبع یا رکورد کنترل می‌شوند؛ وارونگی نیز آزمونِ مستقلِ خطایِ دیررس دارد. تا۴منبع،۸رکورد در هر منبع و۳۲رکورد کل پذیرفته می‌شود. ادامه در مبانی هوش مصنوعی؛ پردازشِ واقعیِ سند یا زیرساختِ اپرا از این مثال نتیجه نمی‌شود.
فایل تمرین و منبع
کد مستقل تمرین و تمام کنترل‌ها؛ Python · ورودی و تمام نتایج اجرای واقعی؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.