تالار گفتمان مانشت

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

Sent from my ST18i using Tapatalk 2

(14 بهمن 1392 12:32 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]سلام.مگه حذف یک عنصر دلخواه از هیپ او n نیست؟من جواب تشریحی ۹۲ دارم گفته جواب گزینه ۴ میشه یعنی هرسه تا جمله با logn انجام میشه

در کل حذف بستگی به این داره که کلید را باید پیدا کنیم و بعد حذف کنیم یا کلید پیداست و ما صرفا باید حذف کنیم

تو این سوال چون گفته حذف کلید دلخواه ، یعنی ما جای کلید را میدونیم کجاست و بر این اساس زمان حذف میشه logn
درج هم که کاملا واضحه از مرتبه logn هست

اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n

(14 بهمن 1392 12:39 ب.ظ)masoud67 نوشته شده توسط: [ -> ]اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n

مرتبه جستجو تو آرایه هیپ که مرتبه میشه logn نمیتونیم از این استفاده کنیم؟

این عکسو ببینید کتاب مقسمیه اینجا هم گفته عنصر دلخواه


Sent from my ST18i using Tapatalk 2

(14 بهمن 1392 12:44 ب.ظ)hosshah نوشته شده توسط: [ -> ]مرتبه جستجو تو آرایه هیپ که مرتبه میشه logn نمیتونیم از این استفاده کنیم؟

مرتبه جستجو در آرایه هیپ مرتب (توجه کن هم آرایه و هم مرتب) مرتبه logn هست
ولی اینجا نه آرایه است و نه مرتب .
آرایه صعودی یک هیپ هست ولی عکسش درست نیست

پس اگر بخوای درخت هیپ را مرتب کنی nlogn زمان لازم داره و یا اگه بخوای هیپ را ببری توی یه آرایه زمان n لازمه پس در کل جستجو در هیپ logn نمیشه

اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n
[/quote]

خب بعد اینکه جستجو کردیم حذف کردیم نباید هیپ مرتب کنیم؟

Sent from my ST18i using Tapatalk 2

بله مرسی

(14 بهمن 1392 12:47 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]این عکسو ببینید کتاب مقسمیه اینجا هم گفته عنصر دلخواه

در مورد این عکس ، خب هر کسی نظر خودشو در مورد واژه دلخواه داره.
شاید من اشتباه میگم ، و شاید مقسمی.
بهر حال من اگه بودم این تست را نمیزدم چون نمیدونستم منظور از عنصر دلخواه چی هست؟
مثلا به نظر من دلخواه اینه که یه عنصر همینجوری عشقی انتخاب کن و حذف کن. این عشقی که میگم نیازی به جستجو نداره . ولی احساس میکنم زمانی که میگه "حذف یک کلید خاص یا مورد نظر" اونوقت این دیگه دلخواه نیست

اینا فقط نظر منه. شاید اشتباه باشه

---

(14 بهمن 1392 12:53 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]خب بعد اینکه جستجو کردیم حذف کردیم نباید هیپ مرتب کنیم؟

نه، هیپ نیاز به مرتب سازی نداره بلکه نیاز به اصلاح داره. یعنی بعد از حذف باید آرایه هیپ یا درخت هیپ را الگوریتم heapify با مرتبه logn روش انجام بدیم که ساختار هیپ حفظ بشه

(14 بهمن 1392 12:53 ب.ظ)masoud67 نوشته شده توسط: [ -> ]

(14 بهمن 1392 12:47 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]این عکسو ببینید کتاب مقسمیه اینجا هم گفته عنصر دلخواه

در مورد این عکس ، خب هر کسی نظر خودشو در مورد واژه دلخواه داره.
شاید من اشتباه میگم ، و شاید مقسمی.
بهر حال من اگه بودم این تست را نمیزدم چون نمیدونستم منظور از عنصر دلخواه چی هست؟
مثلا به نظر من دلخواه اینه که یه عنصر همینجوری عشقی انتخاب کن و حذف کن. این عشقی که میگم نیازی به جستجو نداره . ولی احساس میکنم زمانی که میگه "حذف یک کلید خاص یا مورد نظر" اونوقت این دیگه دلخواه نیست

اینا فقط نظر منه. شاید اشتباه باشه

---

(14 بهمن 1392 12:53 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n

خب بعد اینکه جستجو کردیم حذف کردیم نباید هیپ مرتب کنیم؟

نه، هیپ نیاز به مرتب سازی نداره بلکه نیاز به اصلاح داره. یعنی بعد از حذف باید آرایه هیپ یا درخت هیپ را الگوریتم heapify با مرتبه logn روش انجام بدیم که ساختار هیپ حفظ بشه
[/quote]

پس من نتیجه گرفتم که دلخواه توی این سوال یعنی عشقی حذف کن پس بعدش باید هرم بازسازی کرد با زمان logn درسته؟

Sent from my ST18i using Tapatalk 2

(14 بهمن 1392 12:57 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]پس من نتیجه گرفتم که دلخواه توی این سوال یعنی عشقی حذف کن پس بعدش باید هرم بازسازی کرد با زمان logn درسته؟

این نظر من در مورد واژه دلخواه بود. شاید من دارم اشتباه میکنم
ولی بازسازی هرم logn میشه درسته

خب اونیکه شما گفتی اگه دنبال حذف یک عنصر خاص هستیم با زمان n دنبالش میگردیم بعد حذف، بعد باید heapify انجام بدیم با زمان logn حالا مرتبش چی میشه؟

Sent from my ST18i using Tapatalk 2

(14 بهمن 1392 01:00 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]خب اونیکه شما گفتی اگه دنبال حذف یک عنصر خاص هستیم با زمان n دنبالش میگردیم بعد حذف، بعد باید heapify انجام بدیم با زمان logn حالا مرتبش چی میشه؟

Sent from my ST18i using Tapatalk 2

همون n میشه

از هر دوی شما ممنون و سپاسگذار هستم

Sent from my ST18i using Tapatalk 2

(14 بهمن 1392 01:00 ب.ظ)sahar-it88 نوشته شده توسط: [ -> ]خب اونیکه شما گفتی اگه دنبال حذف یک عنصر خاص هستیم با زمان n دنبالش میگردیم بعد حذف، بعد باید heapify انجام بدیم با زمان logn حالا مرتبش چی میشه؟

اول باید عنصر خاص را پیدا کرد که میشه زمان n. شما تو درخت یه پیمایش بزنی پیداش میکنی که این پیمایش در زمان n انجام میشه. درخت هیپ مثل دودویی نیست که به صورت دودویی بشه جستجو را در logn انجام داد
بعد از پیدا کردن عنصر ، حالا حذفش میکنی که باید اون عنصر را یا با دوران یا با همون heapify برعکس (دقیق یادم نیست چه جوری بود)، عنصر را به برگ میاری و حذف میکنی. چون روال حذف در هیپ معمولا واسه ریشه هست نه واسه کلیدهای داخلی ولی کلیدهای داخلی هم میشه شبیه سازی کرد
پس در کل میشه زمان جستجو n
زمان Heapify یا دوران logn
زمان کل (n + logn = O(n

مرسی کلا ملتفت شدم

Sent from my ST18i using Tapatalk 2