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

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

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

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

(۱۴ بهمن ۱۳۹۲ ۱۲:۳۹ ب.ظ)masoud67 نوشته شده توسط:  اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n

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

(۱۴ بهمن ۱۳۹۲ ۱۲:۴۴ ب.ظ)hosshah نوشته شده توسط:  مرتبه جستجو تو آرایه هیپ که مرتبه میشه logn نمیتونیم از این استفاده کنیم؟

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

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

بله مرسی

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


Sent from my ST18i using Tapatalk 2

(۱۴ بهمن ۱۳۹۲ ۱۲:۴۷ ب.ظ)sahar-it88 نوشته شده توسط:  این عکسو ببینید کتاب مقسمیه اینجا هم گفته عنصر دلخواه

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

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

---

(۱۴ بهمن ۱۳۹۲ ۱۲:۵۳ ب.ظ)sahar-it88 نوشته شده توسط:  خب بعد اینکه جستجو کردیم حذف کردیم نباید هیپ مرتب کنیم؟

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

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

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

Sent from my ST18i using Tapatalk 2

(۱۴ بهمن ۱۳۹۲ ۱۲:۵۳ ب.ظ)sahar-it88 نوشته شده توسط:  اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n

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

Sent from my ST18i using Tapatalk 2
[/quote]

اینجا گفته اعداد دلخواه a1,...,an توی برگ ها هستن پس با توجه به صورت سوال وقتی می گه حذف عنصر دلخواه مثلا ما a5 رو حذف می کنیم
بعد از حذف اخرین عنصر رو جای اون مقدار که حذف کردیم می زاریم و با logn مقایسه (فقط توی اون قسمت که حذف رو انجام دادیم به سمت بالا و اخرین عنصر(می شه ۲logn=Ologn) مقایسه ها رو انجام می دیم) ساختمان داده مثل قبل می مونه دقت کنید این minheap نیست فقط شبیه اون هستش.

(۱۴ بهمن ۱۳۹۲ ۰۱:۲۱ ب.ظ)mehdi.m2 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۱۲:۵۳ ب.ظ)sahar-it88 نوشته شده توسط:  اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n

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

Sent from my ST18i using Tapatalk 2

اینجا گفته اعداد دلخواه a1,...,an توی برگ ها هستن پس با توجه به صورت سوال وقتی می گه حذف عنصر دلخواه مثلا ما a5 رو حذف می کنیم
بعد از حذف اخرین عنصر رو جای اون مقدار که حذف کردیم می زاریم و با logn مقایسه (فقط توی اون قسمت که حذف رو انجام دادیم به سمت بالا و اخرین عنصر(می شه ۲logn=Ologn) مقایسه ها رو انجام می دیم) ساختمان داده مثل قبل می مونه دقت کنید این minheap نیست فقط شبیه اون هستش.
[/quote]


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

(۱۴ بهمن ۱۳۹۲ ۱۲:۵۳ ب.ظ)masoud67 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۱۲:۴۷ ب.ظ)sahar-it88 نوشته شده توسط:  این عکسو ببینید کتاب مقسمیه اینجا هم گفته عنصر دلخواه

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

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

---

(۱۴ بهمن ۱۳۹۲ ۱۲:۵۳ ب.ظ)sahar-it88 نوشته شده توسط:  اما اگر ندونیم اون کلید دقیقا کجاست اول باید پیداش کنیم و بعد حذف کنیم که مرتبه جستجو میشه n چون توی هیپ مرتبه جستجو میشه n

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

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

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

Sent from my ST18i using Tapatalk 2

(۱۴ بهمن ۱۳۹۲ ۱۲:۵۷ ب.ظ)sahar-it88 نوشته شده توسط:  پس من نتیجه گرفتم که دلخواه توی این سوال یعنی عشقی حذف کن پس بعدش باید هرم بازسازی کرد با زمان logn درسته؟

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

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

Sent from my ST18i using Tapatalk 2

(۱۴ بهمن ۱۳۹۲ ۰۱:۰۰ ب.ظ)sahar-it88 نوشته شده توسط:  خب اونیکه شما گفتی اگه دنبال حذف یک عنصر خاص هستیم با زمان n دنبالش میگردیم بعد حذف، بعد باید heapify انجام بدیم با زمان logn حالا مرتبش چی میشه؟

Sent from my ST18i using Tapatalk 2

همون n میشه

(۱۴ بهمن ۱۳۹۲ ۰۱:۰۰ ب.ظ)sahar-it88 نوشته شده توسط:  خب اونیکه شما گفتی اگه دنبال حذف یک عنصر خاص هستیم با زمان n دنبالش میگردیم بعد حذف، بعد باید heapify انجام بدیم با زمان logn حالا مرتبش چی میشه؟

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

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

Sent from my ST18i using Tapatalk 2

(۱۴ بهمن ۱۳۹۲ ۰۱:۰۵ ب.ظ)sahar-it88 نوشته شده توسط:  از هر دوی شما ممنون و سپاسگذار هستم

خواهش میکنم ولی من کاری نکردم جناب مسعود همه کاره بود

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

(۱۴ بهمن ۱۳۹۲ ۰۱:۱۳ ب.ظ)hosshah نوشته شده توسط:  حالا آقا مسعود من یه سوال فنی بپرسم
پیاده سازیه ساختمان داده هیپ توی کامپیوتر مگه نمیتونه به صورت آرایه باشه؟
خب اگه ما یه آرایه هیپ داشته باشیم و همه عملیات رو روی همین انجام بدیم نمیشه؟؟؟

چرا میشه. شما از کامپیوتر جون بخواه.
درخت یا تو آرایه پیاده میشه و یا تو لیست پیوندی. پس هیپ را میشه آورد تو آرایه ولی این هیپی که میاد تو آرایه لزوما مرتب نیست. و اگر مرتبش کنی ، دیگه اون درخت هیپی که تو ساختار شکل هست نخواهد بود

(۱۴ بهمن ۱۳۹۲ ۰۱:۱۸ ب.ظ)masoud67 نوشته شده توسط:  چرا میشه. شما از کامپیوتر جون بخواه.

آره درسته مرتب نیست اما قبول داری باز هم با همون logn میشه یه عنصر رو تو این آرایه پیدا کرد؟

(۱۴ بهمن ۱۳۹۲ ۰۱:۲۰ ب.ظ)hosshah نوشته شده توسط:  آره درسته مرتب نیست اما قبول داری باز هم با همون logn میشه یه عنصر رو تو این آرایه پیدا کرد؟

ولش کن جواب نده
آدمیزاده دیگه سوتی میده

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

Sent from my ST18i using Tapatalk 2