تالار گفتمان مانشت
حذف از Max Heap - نسخه‌ی قابل چاپ

حذف از Max Heap - si.mozhgan - 03 بهمن ۱۳۹۰ ۱۰:۳۱ ق.ظ

یک مکس هیپ با n عنصر را که در آرایه A[1..n] o قرار دارد در نظر بگیرید. مرتبه زمانی الگوریتم حذف عنصر i‌ام از این مکس هیپ به گونه ای که ساختار مکس هیپ را حفظ کند چقدر است؟ (آی تی ۹۰)
۱
nlogn
logn
n

مرتبه حذف از مکس هیپ log n هست . اما پیدا کردن عنصر iام از مرتبه‌ی n هست یا logn ؟

حذف از مکس هیپ - mamat - 03 بهمن ۱۳۹۰ ۰۳:۰۵ ب.ظ

چون عمل حذف از آرایه بر اساس اندیس صورت میگیره پس (O(1 صرف حذف میشه.
بعد برای تبدیل دوباره به MAX-HEAP تابع MAX-HEAPIFY رو صدا میزنیم که از مرتبه (O(Log n هستش.

حذف از Max Heap - Msccom - 11 بهمن ۱۳۹۰ ۰۴:۱۳ ب.ظ

من متوجه نمیشم.بعد از حذف چه عنصری جاش میشینه؟کلا مگه اصول حذف از هیپ از ریشه نیست؟