سوال ۳۷ آی تی ۹۲(max heap)

سلام دوستان
در مورد سوال ۳۷ آی تی ۹۲ که در مورد حذف و درج یه عنصر دلخواه و همچنین کاهش یه مقدار خاص از یکی از عناصر درخت هست و سوال شده که چنتا از این موارد رو میشه با (o(log n انجام داد.
پاسخ هر سه مورد یعنی گزینه ی ۴ هست و من روی حذف یه عنصر دلخواه از درخت شک دارم که log n باشه و اگر میگفت حذف یه عنصر از درخت میشد بگی چون قطعا ریشه باید حذف بشه زمان log n هست اما حالا که گفته یه عنصر دلخواه باید اول درخت رو با زمان n بگردی تا عنصر رو پیدا کنی بعد در زمان log n حذف کنی که میشه (O(n
دوستان کسی میدونه چرا گزینه ۴ شده؟ و گزینه ی ۳ یعنی ۲ مورد درست نیست؟

ارسال: #۲

۰۸ آذر ۱۳۹۲, ۰۲:۵۸ ب.ظ

Riemann پاسخ داده:

RE: سوال ۳۷ آی تی ۹۲(max heap)

حرف شما درسته مثلا اگه بگه ۴ را از این درخت خذف کنید، اول باید توی برگا با O(n) پیداش کنیم بعد خذفش کنیم و با lgn تا هم درخت رو آپ دیت کنیم، ولی درخت چون کامل هست پس توی ارایه به سبک هیپ ذخیره شده و این جا اگه به ما بگن که مثلا A[10] رو حذف کن صرف نظر از مقدارش این با lg n میشه. اون چیزی که توی ذهن شما هست فکر کنم بشه حذف یک عنصر مشخص.

ارسال: #۳

۰۹ آذر ۱۳۹۲, ۱۰:۱۰ ب.ظ

behnam8811413 پاسخ داده:

RE: سوال ۳۷ آی تی ۹۲(max heap)

(۰۸ آذر ۱۳۹۲ ۰۲:۵۸ ب.ظ)Riemann نوشته شده توسط: حرف شما درسته مثلا اگه بگه ۴ را از این درخت خذف کنید، اول باید توی برگا با O(n) پیداش کنیم بعد خذفش کنیم و با lgn تا هم درخت رو آپ دیت کنیم، ولی درخت چون کامل هست پس توی ارایه به سبک هیپ ذخیره شده و این جا اگه به ما بگن که مثلا A[10] رو حذف کن صرف نظر از مقدارش این با lg n میشه. اون چیزی که توی ذهن شما هست فکر کنم بشه حذف یک عنصر مشخص.

ممنون. فک میکنم تمام نکته اش توی این که گفته عناصر در برگ ها هستند و فقط کافیه عمق درخت رو با log n پیمایش کرد و بعدش هم با یه تغییر لینک گره مورد نظر حذف میشه و من به این موضوع دقت نکرده بودم.البته درخت های هیپ کلا کامل هستند و این موضوع مهمی نیست و تاثیری توی جواب نداره
ممنون دوست عزیز مشکل حل شد

ارسال: #۴

۰۸ آذر ۱۳۹۲, ۰۳:۰۸ ب.ظ

explorer پاسخ داده:

RE: سوال ۳۷ آی تی ۹۲(max heap)

حذف عنصر دلخوا پیچیدگی O n Log n داره ولی اینجا
تو صورت سوال گفته که اعداد توی برگها ذخیره شدن

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	فصل HEAP از کتاب ساختمان داده طورانی (پارسه)	tourani	۳۷	۳۶,۷۶۸	۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ آخرین ارسال: hossein4070
	سوالی از max-heap	sir_ams	۳۳	۲۱,۸۵۷	۲۸ دى ۱۳۹۶ ۰۲:۳۴ ب.ظ آخرین ارسال: سیمول
	روش تبدیل یک لیست صعودی از اعداد به max heap	peace2013	۳	۲,۹۶۰	۱۸ فروردین ۱۳۹۶ ۰۲:۴۰ ب.ظ آخرین ارسال: msour44
	تعداد min heapها؟ ۹۰ it	reza.bsh	۲	۲,۲۷۰	۱۳ اردیبهشت ۱۳۹۵ ۰۹:۳۹ ب.ظ آخرین ارسال: reza.bsh
	مرتبه heapsort	مهرگان	۲	۱,۴۷۳	۱۳ بهمن ۱۳۹۴ ۰۸:۳۰ ق.ظ آخرین ارسال: LEA3C
	الگوریتم MIN-MAX	alifarokhi	۲	۴,۵۹۶	۲۵ اردیبهشت ۱۳۹۴ ۰۶:۲۳ ب.ظ آخرین ارسال: gunnersregister
	تعداد مقایسه برای min-heap کردن یک max-heap	rezajam	۴	۴,۱۵۴	۱۲ اسفند ۱۳۹۳ ۰۱:۴۷ ق.ظ آخرین ارسال: sali_h
	آیا این زبان مستقل از متن است؟؟ K<=max(i,j)	Imankhani	۸	۶,۷۹۶	۱۱ بهمن ۱۳۹۳ ۰۷:۴۷ ب.ظ آخرین ارسال: ریحان
	MinMax Heap	rezajam	۱	۱,۴۶۲	۱۰ بهمن ۱۳۹۳ ۰۱:۲۸ ب.ظ آخرین ارسال: A V A
	درخواست حل یک سوال (حذف از min heap)	mmamadi49	۳	۱,۷۰۸	۲۸ دى ۱۳۹۳ ۰۹:۰۶ ب.ظ آخرین ارسال: Densike

سوال ۳۷ آی تی ۹۲(max heap)

سوال ۳۷ آی تی ۹۲(max heap)

RE: سوال ۳۷ آی تی ۹۲(max heap)

RE: سوال ۳۷ آی تی ۹۲(max heap)

RE: سوال ۳۷ آی تی ۹۲(max heap)

Can I see some ID?

Feeling left out?

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

Feeling left out?