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

بچه ها این سوال علوم کامپیوتر 84 هستش
ماکسیمم تعداد مقایسه برای min_heap کردن یک maxheap برابر است با:
جواب :2n
چه جوری میشه 2n ؟

(27 دى 1391 02:03 ق.ظ)azad_ahmadi نوشته شده توسط: [ -> ]سلام.
فکر می کنم به این صورت باشه که هربار یک حذف از مین هیپ داشته باشه(توجه داشته باش که بعد از اون باید تابع heapify فراخوانی بشه تا دوباره مین هیپ رو تازه سازی کنه که هزینه اون O(n هست)، و از عنصر حذف شده یک ماکس هیپ بسازه، که هزینه ساخت یک هیپ هم برابر هست با O(n . درکل میشه 2n که از مرتبه O(n هست.
موفق باشید.

سلام
دقت کنید که درج و حذف در heap از مرتبه log n هست و بنابراین ساخت یک هیپ از مرتبه nlog n خواهد بود و نه n.

(27 دى 1391 01:08 ق.ظ)maryam.raz نوشته شده توسط: [ -> ]بچه ها این سوال علوم کامپیوتر 84 هستش
ماکسیمم تعداد مقایسه برای min_heap کردن یک maxheap برابر است با:
جواب :2n
چه جوری میشه 2n ؟

توجه شود که راه حلی که در کتاب مقسمی هم نوشته شده، غلط می باشد و یا حداقل کامل نیست.

(27 دى 1391 09:21 ق.ظ)آلبالو نوشته شده توسط: [ -> ]

(27 دى 1391 02:03 ق.ظ)azad_ahmadi نوشته شده توسط: [ -> ]سلام.
فکر می کنم به این صورت باشه که هربار یک حذف از مین هیپ داشته باشه(توجه داشته باش که بعد از اون باید تابع heapify فراخوانی بشه تا دوباره مین هیپ رو تازه سازی کنه که هزینه اون O(n هست)، و از عنصر حذف شده یک ماکس هیپ بسازه، که هزینه ساخت یک هیپ هم برابر هست با O(n . درکل میشه ۲n که از مرتبه O(n هست.
موفق باشید.

سلام
دقت کنید که درج و حذف در heap از مرتبه log n هست و بنابراین ساخت یک هیپ از مرتبه nlog n خواهد بود و نه n.

(27 دى 1391 01:08 ق.ظ)maryam.raz نوشته شده توسط: [ -> ]بچه ها این سوال علوم کامپیوتر ۸۴ هستش
ماکسیمم تعداد مقایسه برای min_heap کردن یک maxheap برابر است با:
جواب :۲n
چه جوری میشه ۲n ؟

یک راه می تواند این باشد:
maxheap را در یک آرایه ذخیره می کنیم.
سپس از انتهای آرایه شروع کرده و بین هر سه عدد آخر،عنصر مینیمم را می یابیم که به ۲ مقایسه نیاز است.(سه گره اخر به این خاطر که یک پدر و دو فرزند میتوانیم داشته باشیم).
مینیمم را در اول آرایه minheap مینویسیم.
حال یک عنصر از آرایه maxheap کم شد(با دو مقایسه) و به آرایه minheap اضافه شد.همین پروسه را برای تمام عناصر تکرار میکنیم.n عنصر داریم و به ازای هرکدام نیاز به ۲ مقایسه هست؛ پس تعداد مقایسه ها(O (2n خواهد بود.
یک مثال:
maxheap: 98,96,53,83,43,46,35,19,47
(میتونی درختشو هم برای درک بهتر رسم کنی.)
حال از بین سه تای اخریعنی۴۷ و ۱۹ و ۳۵ مینیمم (۱۹)را انتخاب میکنیم و در ابتدای minheap مینویسیم.دوباره مینیمم سه تای اخر (۴۷و ۳۵ و ۴۶) انتخاب و نوشته میشه.....
و درنهایت:
minheap: 19,35,43,46,47,53,83,96,98

سلام . ممنون. نمی دونم چرا هنگ کرده بودم! بابت جواب اشتباه معذرت می خوام.این جواب هم زیاد مطمئن نیست،اما قابل بحثه
یک راه حل هم شاید به این صورت باشه که ابتدا مین هیپ رو تو یک آرایه قرار بدیم(این قسمت تو جواب نهایی تاثیر نداره!). سپس با جستجوی ترتیبی بزرگترین عنصر رو پیدا کنیم(که البته تو یکی از برگ ها است)، و با گره پیدا شده درخت ماکس هیپ رو ایجاد کنیم. صورت سوال گفته "ماکسیموم کردن تعداد مقایسه" یعنی بنظر به اصل این کاری نداره که کلا تبدیل مین هیپ به ماکس هیپ از چه مرتبه ایه، فقط تعداد بیشترین مقایسه ها رو می خواد. اینجا جستجوی ترتیبی n مقایسه و ایجاد درخت هیپ با n عنصر برابر n هست، و این دوتا بهم وابسته نیستن، n+n = 2n .

(27 دى 1391 11:08 ق.ظ)azad_ahmadi نوشته شده توسط: [ -> ]سلام . ممنون. نمی دونم چرا هنگ کرده بودم! بابت جواب اشتباه معذرت می خوام.این جواب هم زیاد مطمئن نیست،اما قابل بحثه.
یک راه حل هم شاید به این صورت باشه که ابتدا مین هیپ رو تو یک آرایه قرار بدیم(این قسمت تو جواب نهایی تاثیر نداره!). سپس با جستجوی ترتیبی بزرگترین عنصر رو پیدا کنیم(که البته تو یکی از برگ ها است)، و با گره پیدا شده درخت ماکس هیپ رو ایجاد کنیم. صورت سوال گفته "ماکسیموم کردن تعداد مقایسه" یعنی بنظر به اصل این کاری نداره که کلا تبدیل مین هیپ به ماکس هیپ از چه مرتبه ایه، فقط تعداد بیشترین مقایسه ها رو می خواد. اینجا جستجوی ترتیبی n مقایسه و ایجاد درخت هیپ با n عنصر برابر n هست، و این دوتا بهم وابسته نیستن، n+n = 2n .

سلام.دشمنت شرمنده باشه آزادجان.
اول از همه بگم که میخوایم ماکس هیپ رو به مین هیپ تبدیل کنیم نه برعکس.(میدونم تاثیری نداره تو حل ولی برای اینکه هماهنگ باشیم میگم).
اما دقت کنید که آرایه مین هیپ که شما گفتید مرتب نیست، یعنی فقط بار اول که میخواهید جستجوی ترتیبی برای یافتن عنصر ماکزیمم انجام دهید، تعداد مقایسه ها n خواهد بود ولی برای پیدا کردن عناصربعدی n-1 وn-2 و....مقایسه لازمه.پس در کل بهn^2 مقایسه نیاز است و نه n.
اگر هم مثلا بخواهیم همان اول آرایه را مرتب کنیم بازهم زمان بیشتر از n لازمه

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

برای تبدیل max به min فکر کنم بشه o_n :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

---
عکسشم احتمالا o_n میشه

(28 دى 1391 03:53 ق.ظ)csharpisatechnology نوشته شده توسط: [ -> ]برای تبدیل max به min فکر کنم بشه o_n :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

---
عکسشم احتمالا o_n میشه

توجه کنین که موضوعی که در لینک بالا مطرح کردین ارتباطی با سوال این تاپیک نداره، فقط انتخاب عنصر مینیمم از یک درخت مکس هیپ رو گفته(که (O (n میشه) نه تبدیل مکس هیپ به مین هیپ.
ولی ممنون بابت معرفی این سایت.

(27 دى 1391 09:21 ق.ظ)آلبالو نوشته شده توسط: [ -> ]از انتهای آرایه شروع کرده و بین هر سه عدد آخر،عنصر مینیمم را می یابیم که به ۲ مقایسه نیاز است.(سه گره اخر به این خاطر که یک پدر و دو فرزند میتوانیم داشته باشیم).
مینیمم را در اول آرایه minheap مینویسیم.
حال یک عنصر از آرایه maxheap کم شد(با دو مقایسه) و به آرایه minheap اضافه شد.همین پروسه را برای تمام عناصر تکرار میکنیم.n عنصر داریم و به ازای هرکدام نیاز به ۲ مقایسه هست؛ پس تعداد مقایسه ها(O (2n خواهد بود.
یک مثال:
maxheap: 98,96,53,83,43,46,35,19,47

در یک مکس هیپ عنصر مینیمم در یکی از برگ هاست (به تعداد n/2) نه لزوما سه تای آخر؛ مثلا جای 19 رو با 46 عوض و دوباره حل کنید؛

(28 دى 1391 08:44 ب.ظ)Ghiasoddin نوشته شده توسط: [ -> ]در یک مکس هیپ عنصر مینیمم در یکی از برگ هاست (به تعداد n/2) نه لزوما سه تای آخر؛ مثلا جای ۱۹ رو با ۴۶ عوض و دوباره حل کنید؛

ممنون.
عجب داستانی شده!!
ایده حل رو از مقسمی گرفته بودم.متاسفانه خیلی وقتا جواب مقسمی اشتباه هست و یا حتی با جواب سنجش هم هماهنگ نیست.
من کلید سنجش سال ۸۴ رو ندارم ولی با این اوصاف گزینه ۳ یا همون n logn محتمل تر به نظر میاد.

nlogn که مطمئنا هست فقط بهتر میشه یا نه. جای بحث داره. حالا کی میتونه ثابت کنه بهترم میشه؟!!

بنظرم مکس هیپ رابطه مستقیمی با مین هیپ نداره؛
بعبارتی، اینکه یه آرایه بدن و بگن مین هیپش کنید فرقی با حالتی که بدونیم آرایه ورودی مکس هیپه نداره؛
سریع ترین الگوریتم ساخت هیپ هم خطیه (در کتاب پوران الگوریتمش هست)؛ ایدش اینه که هر کدوم از n/2 (سقف) برگ به تنهایی خاصیت هیپ رو دارن؛ پس کافیه هر یک از گره های از n/2 (کف) تا گره ۱ رو یکبار heapify کنیم؛
مرتبش با یه رابطه بازگشتی تعریف میشه که فقط جوابشو یادمه که میشه اوی n (ممکنه 2n جواب دقیقش باشه)؛

(29 دى 1391 02:55 ق.ظ)آلبالو نوشته شده توسط: [ -> ]

(28 دى 1391 08:44 ب.ظ)Ghiasoddin نوشته شده توسط: [ -> ]در یک مکس هیپ عنصر مینیمم در یکی از برگ هاست (به تعداد n/2) نه لزوما سه تای آخر؛ مثلا جای ۱۹ رو با ۴۶ عوض و دوباره حل کنید؛

ممنون.
عجب داستانی شده!!
ایده حل رو از مقسمی گرفته بودم.متاسفانه خیلی وقتا جواب مقسمی اشتباه هست و یا حتی با جواب سنجش هم هماهنگ نیست.
من کلید سنجش سال ۸۴ رو ندارم ولی با این اوصاف گزینه ۳ یا همون n logn محتمل تر به نظر میاد.

جالبه بدونید ایده یوسفی هم همین بوده!!! وگفتن ۲n
ولی از اونجایی که دکتر قدسی هم گفتن ۲n پس درسته
من واسه حلش به این نتیجه رسیدم
اگر درختی داشته باشیم وبخوایم مینیمم هیپ کنیم۲مرحله داره
۱)چون واسه هر گره با فرزند چپ وراستش ۲مقایسه لازمه تا مینیمم بین آنها پیدا بشه پس به ازای زیردرخت شامل ۳گره ،۲مقایسه لازمه که این تعداد تقریبا برابر nمیشه
علاوه بر این تغییر و یافتن مینیمم در زیردرختهای بالاتر ممکنه باعث تغییر در زیردرختهای پایین تر بشه(که البته اگه زیر درخت چپ وراست داشته باشیم فقط در یکی از اونها تغییر داریم) واین تغییر تا ارتفاع اون زیر درخت ممکنه پیش بره
که اگه واسه یه درخت مثال بزنید یه چیزی نزدیک به n میشه
که در مجموع ۲n میشه (البته در بدترین حالت)
واسه این درخت که ۱۱ گره داره و۵زیر درخت
در مرحله اول۱۱ (nمقایسه
در مرحله دوم ۸تا
که مجموعا ۱۸ میشه و به ۲n نزدیکه

فکر می کنم جواب این مسئله از طریق "هیپ درجا " یا" ساخت هیپ به روش جوان ترین پدر "باشه .
که اصطلاح ساخت هیپ به روش جوان ترین پدر در کتاب آقای مقسمی اومده و ص 257 توضیح دادن.
و اصطلاح "هیپ درجا " در کتاب آقای قدسی اومده و در ص337 اثبات شده که از مرتبه (O(n هست.

الگوریتم:
BuildHeap(A
for (i=[lengthA downto 1
do MaxHeapify(A,i

که نحوه کار( MaxHeapify(A,i هم ص242 آقای قدسی اومده و به این صورت هست که ابتدا اندیس بزرگترین فرزند i یا( bigchild(i رو به دست میاریم اگر کلید i از کلیدbigchildکمتر نباشد کار به اتمام رسیده ولی اگر کلید i از کلید bigchild کمتر باشد در ان صورت این دو کلید را با هم عوض می کنیم و با فراخوانی MaxHeapify(A, bigchild از اندیس bigchild تا آخر آرایه را به صورت هرم در می آوریم.

---

(27 دى 1391 09:21 ق.ظ)آلبالو نوشته شده توسط: [ -> ]

(27 دى 1391 02:03 ق.ظ)azad_ahmadi نوشته شده توسط: [ -> ]سلام.
فکر می کنم به این صورت باشه که هربار یک حذف از مین هیپ داشته باشه(توجه داشته باش که بعد از اون باید تابع heapify فراخوانی بشه تا دوباره مین هیپ رو تازه سازی کنه که هزینه اون O(n هست)، و از عنصر حذف شده یک ماکس هیپ بسازه، که هزینه ساخت یک هیپ هم برابر هست با O(n . درکل میشه ۲n که از مرتبه O(n هست.
موفق باشید.

سلام
دقت کنید که درج و حذف در heap از مرتبه log n هست و بنابراین ساخت یک هیپ از مرتبه nlog n خواهد بود و نه n.

(27 دى 1391 01:08 ق.ظ)maryam.raz نوشته شده توسط: [ -> ]بچه ها این سوال علوم کامپیوتر ۸۴ هستش
ماکسیمم تعداد مقایسه برای min_heap کردن یک maxheap برابر است با:
جواب :۲n
چه جوری میشه ۲n ؟

یک راه می تواند این باشد:
maxheap را در یک آرایه ذخیره می کنیم.
سپس از انتهای آرایه شروع کرده و بین هر سه عدد آخر،عنصر مینیمم را می یابیم که به ۲ مقایسه نیاز است.(سه گره اخر به این خاطر که یک پدر و دو فرزند میتوانیم داشته باشیم).
مینیمم را در اول آرایه minheap مینویسیم.
حال یک عنصر از آرایه maxheap کم شد(با دو مقایسه) و به آرایه minheap اضافه شد.همین پروسه را برای تمام عناصر تکرار میکنیم.n عنصر داریم و به ازای هرکدام نیاز به ۲ مقایسه هست؛ پس تعداد مقایسه ها(O (2n خواهد بود.
یک مثال:
maxheap: 98,96,53,83,43,46,35,19,47
(میتونی درختشو هم برای درک بهتر رسم کنی.)
حال از بین سه تای اخریعنی۴۷ و ۱۹ و ۳۵ مینیمم (۱۹)را انتخاب میکنیم و در ابتدای minheap مینویسیم.دوباره مینیمم سه تای اخر (۴۷و ۳۵ و ۴۶) انتخاب و نوشته میشه.....
و درنهایت:
minheap: 19,35,43,46,47,53,83,96,98

این راه حل توی کتاب آقای مقسمی اومده و با مثال نقص میشه گفت که درست نیست.
اگر به جای 43, 46 به ترتیب 4و 5قرار بدیم راه حل جواب درست نمیده! درست نمی گم؟

هر گره تقریبا 2 مقایسه
در نتیجه n گره میشه 2n