برای میانهٔ دقیقِ جریانِ افزایشی، دو heap می‌توانند دو نیمهٔ مرتب را نمایندگی کنند. پس از هر ورودی، مرزِ دو نیمه برای محاسبهٔ میانه کافی است؛ اما همهٔ مقدارها همچنان نگه داشته می‌شوند. این روش حافظهٔ ثابت یا خلاصهٔ تقریبیِ صدک نیست. فایلِ تمرین هر درج، جابه‌جایی و میانهٔ پیشوند را واقعاً ثبت می‌کند.
دو نیمه چه قاعده‌ای دارند؟
نیمهٔ پایین نباید مقداری بزرگ‌تر از نیمهٔ بالا داشته باشد. تعدادِ اعضای پایین یا برابرِ بالا است یا یک عدد بیشتر. در Python۳٫۱۲، heapq یک min-heap می‌دهد؛ برای دیدنِ بزرگ‌ترین عضوِ پایین، عددهای منفیِ آن نیمه را ذخیره می‌کنیم.
نمایشِ heap فهرستِ کاملاً مرتب نیست؛ فقط ریشهٔ آن عنصرِ کمینهٔ قرارداد است. در فایل برای خواندنِ دفتر، نسخهٔ مرتبِ نمایشیِ مقدارهای هر نیمه نیز ساخته می‌شود. این مرتب‌سازیِ اضافی بخشی از گزارشِ کوچک است، نه ادعایِ هزینهٔ همان الگوریتمِ درج.
شش ورود را دنبال کنیم
جریانِ ساختگی۵،۱،۹،۲،۲و۸است. پس از۵، میانه۵و پس از۱، میانهٔ دو مقدار۳است. با ورود۹، پایین باید دو عضو و بالا یک عضو داشته باشد؛ میانه۵می‌شود. دو۲تکراری رکوردِ مستقل‌اند و حذف نمی‌شوند.
میانه‌های تمام پیشوندها به‌ترتیب۵،۳،۵،۷/۲،۲و۷/۲هستند. در حالتِ فرد، ریشهٔ بزرگینهٔ پایین جواب است؛ در حالتِ زوج، میانگینِ دو ریشه با Fraction حساب می‌شود. گردکردنِ زودهنگام، قراردادِ میانهٔ دقیق را عوض می‌کند.
بعد از درج، تعادل را برگردانیم
عددِ تازه با مرزِ پایین مقایسه و به نیمهٔ مناسب وارد می‌شود. اگر اندازه‌ها از اختلافِ صفر یا یک خارج شوند، یک ریشه از نیمهٔ بزرگ‌تر به دیگری انتقال می‌یابد. دفترِ هر گام نامِ حرکت، اندازه‌ها و ریشه‌های نهایی را ثبت می‌کند.
سه invariant واقعاً کنترل می‌شوند: جرمِ چندمجموعهٔ دو heap با تمام ورودی‌های دیده‌شده برابر است؛ هر عضوِ پایین از هر عضوِ بالا بزرگ‌تر نیست؛ و اختلافِ اندازه در قراردادِ مجاز است. فقط برابرشدنِ یک عددِ میانه برای یافتنِ گم‌شدنِ رکورد کافی نیست.
میانهٔ قبلی را میانگین نگیریم
پس از ورودی‌های۵و۱، میانه۳است. میانگینِ آن با ورودیِ تازه۹، عدد۶می‌دهد؛ ولی میانهٔ [۵،۱،۹] برابر۵است. پس نگه‌داشتنِ فقطِ میانهٔ قبلی و شمارنده، همان به‌روزرسانیِ میانگین نیست و اطلاعاتِ کافیِ این قرارداد را ندارد.
Welford حالتِ میانگین و واریانس را به‌روز می‌کند؛ میانه را از همان دو عدد تحویل نمی‌دهد. تفسیرِ میانگین و میانهٔ تماس نیز مسئلهٔ انتخابِ شاخص است؛ اینجا ساختمانِ داده و درجِ متوالی اجرا می‌شود.
هر پیشوند با مرتب‌سازیِ مستقل کنترل می‌شود
oracle تمامِ پیشوند را جدا مرتب و مقدارِ میانی یا میانگینِ دو خانه را برمی‌دارد. همهٔ۱۰۹۳رشتهٔ طولِ صفر تا۶روی مقادیرِ−۱،صفر و۱اجرا شده‌اند؛ در مجموع۶۰۱۵پیشوندِ غیرخالی با دو heap برابر بوده‌اند. این شمارشِ واقعی است و زمان‌سنجیِ سامانهٔ بزرگ نیست.
ورودیِ خالی None می‌دهد؛ نبود مشاهده را صفر نمی‌نامیم. پنج آزمون، بولین، اعشار،NaN،نامتناهی و بیش از۱۶ورود را رد می‌کنند. مقدارِ صحیح با قدرمطلقِ حداکثر۱۰۰۰پذیرفته می‌شود؛ حذفِ پنجره‌ای و جریانِ بی‌پایان پیاده نشده است.
حافظهٔ این میانهٔ دقیق O(n) است؛ JSON کامل و oracle نیز فضای اضافی دارند. صدکِ انتظار تعریفِ دیگری دارد. ادامه در آموزش هوش مصنوعی؛ این مثال نتیجهٔ گزارشِ عملیاتی یا قابلیتِ تأییدشدهٔ پنلِ اپرا نیست.
فایل تمرین و منبع
کد مستقل تمرین و تمام کنترل‌ها؛ Python · ورودی و تمام نتایج اجرای واقعی؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.