حذف از Max Heap

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

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

ارسال: #۲

۰۳ بهمن ۱۳۹۰, ۰۳:۰۵ ب.ظ

mamat پاسخ داده:

حذف از مکس هیپ

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

ارسال: #۳

۱۱ بهمن ۱۳۹۰, ۰۴:۱۳ ب.ظ

Msccom پاسخ داده:

حذف از Max Heap

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

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	حذف اکانت	Alireza_1387	۴	۵,۷۰۳	۱۴ آذر ۱۴۰۱ ۰۸:۲۱ ب.ظ آخرین ارسال: shirin.kh90
	حذف درس برای خواندن کنکور ارشد	sima84	۴	۵,۰۷۷	۲۶ اردیبهشت ۱۳۹۹ ۰۹:۰۰ ب.ظ آخرین ارسال: عزیز دادخواه
	فصل HEAP از کتاب ساختمان داده طورانی (پارسه)	tourani	۳۷	۳۹,۹۵۹	۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ آخرین ارسال: hossein4070
	حذف از b tree کمک لطفا	Sanazzz	۰	۱,۸۶۶	۱۱ بهمن ۱۳۹۷ ۰۹:۳۴ ب.ظ آخرین ارسال: Sanazzz
	حذف ضمیر موصولی ☹	jinubo	۲	۷,۰۲۰	۰۱ اردیبهشت ۱۳۹۷ ۰۶:۴۳ ب.ظ آخرین ارسال: jinubo
	سوالی از max-heap	sir_ams	۳۳	۲۳,۸۱۹	۲۸ دى ۱۳۹۶ ۰۲:۳۴ ب.ظ آخرین ارسال: سیمول
	حذف اضطراری دو درس در ارشد	asalimi	۰	۲,۵۹۹	۰۸ آذر ۱۳۹۶ ۰۲:۳۲ ق.ظ آخرین ارسال: asalimi
	حذف وزارت علوم	H-Arshad	۰	۱۰	۲۱ آبان ۱۳۹۶ ۰۱:۵۲ ب.ظ آخرین ارسال: H-Arshad
	با بدهی استقلال و پرسپولیس چند کلاس کپری حذف می شود؟	H-Arshad	۰	۴	۱۱ آبان ۱۳۹۶ ۱۲:۰۹ ق.ظ آخرین ارسال: H-Arshad
	حذف فول بک آپ از هاست سی پنل	targol	۰	۱,۸۲۷	۲۴ اردیبهشت ۱۳۹۶ ۰۸:۴۹ ب.ظ آخرین ارسال: targol

حذف از Max Heap

حذف از Max Heap

حذف از مکس هیپ

حذف از Max Heap

Can I see some ID?

Feeling left out?

رمزت رو فراموش کردی؟

Feeling left out?