(۰۸ بهمن ۱۳۹۴ ۰۲:۰۶ ق.ظ)sixsixsix نوشته شده توسط:  این سوال، قبلا سوال خودم بوده
من توضیح میدم، سعی کن مثالی واسه خودت بزنی خیلی راحت میفهمی

ببین برای اینکار نیاز به یه حافظه کمکی به اندازه k داری وگرنه نمیشه این کار رو انجام داد.
در وهله دوم)
ما یه minheap اولیه داریم که مسلماً میدونیم کوچکترین عنصر آن در ریشه است
بایــد یه minheap دیگه خودمون بسازیم (به اندازه k) ، اسمشو مثلا میذاریم A
توی A باید مینیم عنصرهای مین هیپ اصلی رو قرار بدیم. در ابتدا توی A فقط عنصر ریشه از مین هیپ رو داریم. هر بار از A کوچکترین عنصر رو حذف میکنیم و دو عنصر فرزند آنرا که در مین هیپ اصلی قرار دارند در A اضافه میکنیم. مرتبه این کار برای هر بار logk هست (چون شامل یه حذف از مین هیپ A (به اندازه k) و دو درج در مین هیپ A (به اندازه k) هست که میشه ۳logk=O(logk))
اگه این عمل رو k بار انجام بدیم دقیقا عنصر ریشه مین هیپ A در مرحله k ام جواب است. که هر مرحله logk هست که میشه klogk
نمیدونم متوجه شدی یا نه ، من تو توضیح دادن خیلی ضعیفم
سوالی بود بپرس دقیقتر بگم
راستی بگم من این جواب رو قبلا از یکی از ساب سایت های stackoverflow پیدا کردم.