توی کتاب مقسمی تعداد مقایسه برای minheap کردن یک maxheapرو O(2n گفته. ولی یه راه حلی گفته که فکر می کنم درست نیست.
باید از راه "ساخت درخت نیمه مرتب به روش جوان ترین پدر" یا همون "هیپ درجا "بریم که گره های از ۱+[n/2]تا ۱ رو بررسی می کنه که هیپ باشن؟
همین سوال رو من زودتر از شما پرسیدم بچه ها دارن بحث میکنن
بیاین اینجا
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
همون لینک بالایی:
هر گره تقریبا ۲ مقایسه
در نتیجه n گره میشه ۲n مقایسه