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

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

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

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

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

---

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

---

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