با عرض سلام
دوستان سوال زیر، مگه منظورش الگوریتم heapify نیست ؟ و مگه الگوریتم heapify برای گره های از ۰ تا [tex]\lfloor\frac{(n)}{2}\rfloor[/tex]
نیست ؟
پس چرا تا گره ۶ رفته بجای ۵ ؟ تعداد مقایسه ها رو هم بزرگواری می فرمایید یه توضیح بدید ؟
با تشکر
سلام
۶ یا ۵ گرفتن اخرین نود داخلی بستگی به شروع اندیس ارایه از ۰ یا ۱ دارد.
جواب این تست ۱۸ می شود نه ۱۰ یعنی گزینه ۴
در واقع ۱۰ حداکثر تعداد تعویض است نه مقایسه
برای ساختن Min heap با heapify (چون تمام اعداد در ابتدا در دسترس است) از اخرین عنصر داخلی با اندیس [tex]\lfloor(\frac{n}{2})\rfloor[/tex] تا عنصر با اندیس ۱ (برای راحتی شروع ارایه با ۱ فرض می شود) تابع heapify را صدا می زنیم
با اجرا heapify روی نود با اندیس ۶ (اخرین نود داخلی )حداکثر یک مقایسه
روی نود با اندیس۵ دو مقایسه(یک مقایسه بین فرزندان برای یافتن کوچکترین و یک مقایسه بین کوچکترین فرزند با والد)
روی نود با اندیس ۴ دو مقایسه
روی نود با اندیس ۳ سه مقایسه(یک مقایسه بین اندیس های ۶ و۷ و یک مقایسه بین کوچکترین فرزند با نود اندیس ۳ و فراخوانی دوباره heapify روی نود با اندیس۶ که یک مقایسه دارد توجه شود حداکثر مد نظر است به همین دلیل فرض کردیم به سمت شاخه طولانی تر بریم)
روی نود با اندیس ۲ چهار مقایسه
روی نودبا اندیس ۱(ریشه) ۶ مقایسه
جمع کل ۱۸ مقایسه
در کل اگر بخواهیم یک ارایه با n عنصر را به صور ت کارا به min heap تبدیل کنیم نیاز به حداقل n مقایسه داریم با همین نکته گزینه اول و دوم رد می شود.
دوست گرامی
از شما بسیار سپاسگزارم به خاطر کمک ها و راهنمایی های بی دریغتون و اینکه همیشه سوالات رو با حوصله و دقت جواب می دید
ان شاالله شاد و موفق و سربلند باشید