[quote='T.A' pid='154781' dateline='1358510584']
حذف یک عنصر دلخواه از heap از چه مرتبه ای هست و چگونه انجام می شه؟
(توی کتاب مقسمی نوشته از مرتبه O(n هست.
و یه جای دیگه گفته "جست و جو و یافتن عنصر بعدی" از مرتبه O(nlogn
چرا و چجوری؟
نگاه گنید اگه شما می خواین ریشه هیپ را حذف کنین مرتبه میشه log. به این دلیل که شما ابتدا ریشه رو حذف می کنین و سپس آخرین نودو جایگزین اون می کنین و از ریشه جدید شروع می کنین و با مقایسه بین دو فرزندش، بزرگتر رو انتخاب می کنین و جای اونو با ریشه عوض می کنین و این کار رو در طول مسیر انجام میدید تا هیپ به شکل صحیح دربیاد که به علت اینکه ارتفاع هیپ log ای هست میشه log.
اما اگه یه عنصر دلخواه رو می خواید حذف کنید که نمی دونید کجاست یا اصلا هست یا نه. باید اولش پیداش کنین و سپس اونو به عنوان ریشه فرضی درنظر بگیرین و همون کارای بالا رو برای این زیردرخت انجام بدین. بنابراین مرتبه میشه جستجوی عنصر O(n) و سپس حذف اون log که بنابراین میشه O(n+logn) یا O(n)
O(nlogn) زمانی هست که می خواید عناصر رو تک تک از ریشه حذف کنین که برای مرتب سازی با هیپ کاربرد داره.

از جوابتون ممنون!
فقط منظورم از جست و جو و یافتن عدد بعدی ،پیدا کردن عدد بعدی (کوچکترین عدد بزرگتر از X) در هیپ هست که اقای مقسمی توی کتابش مرتبه اش رو (O(nlogn گفته!
لطفا در مورد این یکی هم اگه میتونید توضیح بدین.

چطور گفته nlogn ?!!
به نظر من در درخت Heap برخلاف درخت جستجوی دودویی که کوچکترین عدد بزرگتر می تونه log ای به دست بیاد به شرط اونکه هر گره اشاره گر به پدر نیز داشته باشه اون نمی تونه بنا به خاصیتش. شما فرض کنین می خواین کوچکترین عدد بزرگتر از x را در هیپ بیابین اون می تونه هر جایی باشه پس اگه جای x رو نمی دونین باید با o(n) بیابین و سپس با o(n) دنبال کوچکترین عدد بزرگتر از x بگردین. پس میشه o(n) ?!!
به این دلیل پس از یافتن x پیدا کردن کوچکترین عدد بزرگتر از x میشه اوی n چون تنها کافیه شما هر گره رو با x مقایسه کنین و عدد موردنظرو پیدا کنین.

---

در ضمن یه چیزو یادم رفت بگم اگه نود x ریشه درخت ماکس هیپ باشه اونوقت حتما بزرگترین عدد کوچکتر از x میشه یکی از فرزنداش و اگه x در سطح ۲ باشه اونوقت بزرگترین عدد کوچکتر از آن میشه یکی از دو فرزندهاش و یا برادرش و یا یکی از بچه های برادرش، همین طور الی..

(o(lgn
=========
جزوه ی قدسی
ص ۶۵
--
توی PDF میشه صفحه ی ۹۱

پیاده سازی هیپ میشه o(n