به نام خدا
سلام
سه تا سایت هست که آدرسشون رو میدم اونا توضیح دادن. ولی منم در اینجا سعی میکنم فارسی این موضوع رو توضیح بدم.
خب میانه که یعنی یه لیستی از اعداد داشته باشیم، اونا رو مرتب کنیم و در نهایت عدد وسط میشه میانه.
همونطور که پیداست اگه بخوایم لیست رو مرتب کنیم مرتبه اش از n رد میزنه چه برسه log n
ما در اینجا داریم روی بدست آوردن میانه از روی داده های استریم صحبت میکنیم! یعنی یه سری داده که پشت سر هم وارد برنامه میشن و ما حتی اندازه شون رو هم نمیدونیم. کاری که ما انجام میدیم اینه که در هر لحظه که داده جدید وارد میشه میانه جدید هم محاسبه میشه.
مثلا اگه اول 2 وارد بشه میانه همون 2 هست
بعد 4 وارد بشه میانه میشه 3
بعد 5 وارد بشه میانه میشه 4 (عدد وسطی)
و به همین ترتیب ادامه داره
حالا میریم سراغ توضیح روش خودمون:
فرض کنید در ابتدا عدد 20 وارد میشه! میانه همون 20 خواهد بود
بعد عدد 21 وارد بشه. میانه میشه 20.5 و بعد عدد 19 وارد بشه میانه میشه 20 دوباره
منظورم اینه که در هر دو دیتای ورودی یکی بزرگتر از میانه باشه یکی کوچیک تر از میانه، میانه تغییر نمیکنه خوشبختانه
اعداد بزرگتر از میانه رو توی درخت minHeap ذخیره میکنیم و اعداد کوچیکتر از میانه رو توی درخت Max Heap. دلیلش اینه که شما اگه یه لیست مرتبی به شکل زیر داشته باشید
3 , 5 , 7 , 8 , 10 , 13 , 14 , 15 , 17
که میانه در اینجا 10 هست. اعداد ما قبل میانه همه از میانه کوچیکترن ولی عدد قبل از میانه بزرگترین عدد بین اعداد کوچیک هست!
همینطور همه اعداد بعد از میانه از میانه بزرگتر هستن! ولی عدد بعد از میانه کوچیکترین عدد در بین اعداد بزرگ هست.
پس اینجوری میشه که اگه ما خواستیم یه عدد تازه وارد کنیم و میانه رو محاسبه کنیم! عدد جدید رو با مقدار فعلی میانه محاسبه میکنیم! اگه بزرگتر بود میره سمت راست یعنی توی minHeap و اگه کوچکتر بود میره سمت چپ یعنی maxHeap
دو تا نکته!
1- خود میانه هم توی یکی از max heap یا min heap است ولی ممکنه ما برای راحتی کار اونو توی یه متغیر دیگه هم نگاه داری کنیم!
2- تعداد عناصر موجود توی minHeap و maxHeap همیشه باید باهم برابر یا حداکثر اختلاف یکی داشته باشن. (اختلاف تعداد عناصر یا صفر یا یک باشد) چون میانه همیشه عدد وسط هست! در لیست اعداد مرتب شده بالا، اعداد 13 و 14 و 15 و 17 توی min Heap هستند که عنصر روت آن مینیمم آنها یعنی 13 خواهد بود. همچنین اعداد 3 و 5 و 7 و 8 توی max Heap هستن که عنصر روت آن بزرگترین آنها یعنی 8 خواهد بود.
در اصل 10 هم باید توی یکی از هر دو باشه! مثلا 10 میتونه توی min Heap باشه که در این صورت میشه روت یا میتونه توی max Heap باشه که بازم میشه روت!
حالا چطور تشخیص بدیم میانه کیه؟
خیلی راحته اگه اختلاف بین دوتا درخت هیپ 1 بود (یعنی یکی بزرگتر از دیگری بود) عدد میانه عنصر روت همون درخت بزرگتره است.( مثلا در همینجا اگه 10 بره توی مین هیپ، مین هیپ یکی بیشتر از مکس هیپ میشه و عنصر روتش که همون 10 باشه میشه میانه. یا بالعکس)
اما اگه اختلاف دو تا درخت 0 بود (یعنی اندازه دو تا درخت برابر بودن) میانه میشه میانگین عنصر روت هر دو درخت.
نکته اینجاست که نباید بزاریم اختلاف دو تا درخت از 1 بیشتر بشه!
مثلا ممکنه اعدادی که وارد میشن همه از میانه بزرگتر باشن! مثلا
1, 2, 3, 4, 5, 6, 7, 8, 9
همیجوریه! هروقت میانه محاسبه میشه عدد بعدی که وارد میشه حتما بزرگتر از میانه است! یعنی همش میخواد بره تو min Heap. بنابراین ما نباید بزاریم این اتفاق بیوفته چون دیگه اختلاف از 1 بیشتر بشه به ما دیگه میانه رو نمیده.
پس باید قبل از اینکه عدد ورودی رو توی اون درختی که همین الان با اختلاف 1 بزرگتر از اون یکیه درج کنیم، عنصر روت اون رو حذف کنیم و در اون یکی درخت درج کنیم! حالا اون درخت کوچیکه بزرگتر میشه و اگه عنصر جدید رو توی اون درختی که اول بزرگتر بود حالا کوچیکتر شد درج کنیم اختلاف تعداد عناصر 0 میشه 
پس نکته اصلی اینه که هیچوقت نباید بزاریم اختلاف تعداد عناصر یک درخت بیش از 1 بشه! حتی این اتفاق نباید برای 1 ثانیه هم بیوفته
توضیحات تکمیلی توی سه تا سایت زیر هست
Median of Stream of Running Integers using STL
Median in a stream of integers (running integers)
How to implement a Median-heap
اینم کد من با زبان C# فکر کنم درست کار کنه! (بیشتر به MidHeap.cs توجه کنید)
موفق باشید
