سلام لطفا اول نحوه الگوریتم heapifyرو بگید بعد هم حل تست ممنون
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۰ آذر ۱۳۹۳ ۱۱:۱۶ ب.ظ)abji22 نوشته شده توسط: سلام لطفا اول نحوه الگوریتم heapifyرو بگید بعد هم حل تست ممنون
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
دوست عزیز من پاسخ خودمو میگم نمیدونم چقد درسته بعد دوستان پاسخ درستو احتمالا میزارن
Maxheapifiبطور ساده برای حفظ ویژگی maxheap هست که ورودیش آرایه Aواندیس iهست وزمانیکه فراخوانی میشه فرض اینه که فرزندان چپ و راستش خودشون مکس هیپ هستند ولی خود [¡]A این ویژگی رو نداره.
بطور ساده این روال میاد روی عنصر مورد نظر فرزند بزگتر رو با دو مقایسه پیدا میکنه و جایگزین عنصر مورد نظر میکنه واینبار با اندیس فرزندی که جابجا شده فراخوانی میشه و این روند ادامه پیدا میکنه تا حداکثر به ارتفاع درختlog nبرای یک عنصر زمان میبره.
برای تبدیل یک آرایه به هیپ از همین روال استفاده میشه وبا اندیس اولین گره ای که برگ نیست شروع میشه و با زمان O(n آرایه رو به مکس هیپ تبدیل میکنه.
در این سوال به نظرم گزینه ۴ صحیح باشه ،البته گزینه ۲ به جواب نزدیکه اما چون بدترین حالت گفته فک کنم مربوط به همون آخرین گره غیر برگ باشه.
بازم میگم شاید درست نباشه،حالا سایر دوستان بهتر جواب میدن