دوستان مرتبه اجرایی حذف مینیمم از ماکس هیپ چیه؟
مین که مسلما در برگهاست و با هزینه n پیدا میشه بعد حذف مستقیم با مرتبه ۱ بعدم
باید هیپ فای کرد نه؟ چون درسته مینیمم ...برگ هستش اما با حذفش درخت از کاملی در بیاد
یعنیnلوگn?
سلام
من فک میکنم چون عنصر مینیمم حتماً در برگها قرار گرفته , برای حذفش هم باید برگها رو مقایسه کنیم تا پیداش کنیم , یعنی تعداد مقایسه های بین برگها.... که در بدترین حالت فک کنم تعداد برگها [tex]\frac{n}{2}[/tex] باشه , در نتیجه کمترین زمان [tex]O(n)[/tex] باید بشه...
اگه اشتباه میکنم دوستان بگن لطفاً
خب باید هیپ فای کردش نه؟
اما نه هیپ فای هست که... خب پس ممکنه با حذف یه برگ درخت از کاملی ممکنه در بیاد نه؟ اونو چه کار کنیم؟
دوستان خواهشا جواب بدید پس...
(۰۵ بهمن ۱۳۹۳ ۰۵:۴۹ ب.ظ)ریحان نوشته شده توسط: دوستان خواهشا جواب بدید پس...
======
زهرا خانم کاملا درست میگن
ما از n/2 +1 تا n رو همه ر وباهنم مقایسه میکنیم ومین انتخاب میشه دقیقا سقف n/2
تتا چون دقیقا نصف عنصرها ر وباید همشونو ببینیم
خب هیپ فای نمیخواد؟
(۰۵ بهمن ۱۳۹۳ ۰۵:۵۸ ب.ظ)ریحان نوشته شده توسط: خب هیپ فای نمیخواد؟
نه وقتی همه گره های سطح اخر رو با مرتبه ان مقایسه کردی و مین رو انتخاب کردی حذفش کن عنصر اخر رو بزار سرجاش اگر لازم بود تا ریشه مقایسه کن بر و.بالا
به فرضم که جابجا بشه هیپیفای هم بشه مرتبه n اولی بیشتر از هیپیفای با مرتبه logn هست