(۰۷ اسفند ۱۳۹۵ ۱۱:۴۷ ب.ظ)arash691 نوشته شده توسط:  

یک روش اینه که k بار عمل ExtractMin انجام بدیم که از مرتبه [tex]O(klogn)[/tex] خواهد شد ولی راه حل بهتری داره که میشه از مرتبه [tex] O(klogk)[/tex]

این تیپ سوال تو کتاب ۶۰۰ مسئله با فرم دیگه ای بیان شد که گفته بود logn امین بزرگترین عنصر رو میخواهیم پیدا کنیم ( صفحه ۵۹ )

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سلام
این سوال کپی سوال دانشگاه MIT هست.
جواب گزینه ی چهار است
[tex]O(klogk)[/tex]

---

توضیحات به همراه مثالش هم در جزوه ی هیپ که اقای طورانی گذاشتن هستش.
اون جزوه رو دانلود کنید و بخونید حتما. بعید میدونم با خوندن اون جزوه سوالی از هیپ رو نشه پاسخ داد.

---

یک راه حل دیگه اینه که :
شما عناصر هرم رو بچینید توی یک آرایه و با توجه به اینکه عناصر هرم لزوما به صورت مرتب در آرایه قرار نمیگیرند ما یک ارایه نا مرتب داریم باید از مرتب سازی مقایسه ای که مرتبه ی کلی آن [tex]\Omega(n\: log\: n)[/tex] است استفاده کنیم
تعداد عناصر هم k تا داده شده که k کمتر یا مساوی مقدار رادیکال n هست. رد گزینه سه.
اگر [tex](k\: log\: \sqrt{n})[/tex] بود در گزینه ها به نظرم اونم میتونست پاسخ باشه.