بچه ها این سوال علوم کامپیوتر ۸۴ هستش
ماکسیمم تعداد مقایسه برای min_heap کردن یک maxheap برابر است با:
جواب :۲n
چه جوری میشه ۲n ؟
(۲۷ دى ۱۳۹۱ ۰۲:۰۳ ق.ظ)azad_ahmadi نوشته شده توسط: سلام.سلام
فکر می کنم به این صورت باشه که هربار یک حذف از مین هیپ داشته باشه(توجه داشته باش که بعد از اون باید تابع heapify فراخوانی بشه تا دوباره مین هیپ رو تازه سازی کنه که هزینه اون O(n هست)، و از عنصر حذف شده یک ماکس هیپ بسازه، که هزینه ساخت یک هیپ هم برابر هست با O(n . درکل میشه ۲n که از مرتبه O(n هست.
موفق باشید.
دقت کنید که درج و حذف در heap از مرتبه log n هست و بنابراین ساخت یک هیپ از مرتبه nlog n خواهد بود و نه n.
(۲۷ دى ۱۳۹۱ ۰۱:۰۸ ق.ظ)maryam.raz نوشته شده توسط: بچه ها این سوال علوم کامپیوتر ۸۴ هستشتوجه شود که راه حلی که در کتاب مقسمی هم نوشته شده، غلط می باشد و یا حداقل کامل نیست.
ماکسیمم تعداد مقایسه برای min_heap کردن یک maxheap برابر است با:
جواب :۲n
چه جوری میشه ۲n ؟
(۲۷ دى ۱۳۹۱ ۰۹:۲۱ ق.ظ)آلبالو نوشته شده توسط:(27 دى ۱۳۹۱ ۰۲:۰۳ ق.ظ)azad_ahmadi نوشته شده توسط: سلام.سلام
فکر می کنم به این صورت باشه که هربار یک حذف از مین هیپ داشته باشه(توجه داشته باش که بعد از اون باید تابع heapify فراخوانی بشه تا دوباره مین هیپ رو تازه سازی کنه که هزینه اون O(n هست)، و از عنصر حذف شده یک ماکس هیپ بسازه، که هزینه ساخت یک هیپ هم برابر هست با O(n . درکل میشه ۲n که از مرتبه O(n هست.
موفق باشید.
دقت کنید که درج و حذف در heap از مرتبه log n هست و بنابراین ساخت یک هیپ از مرتبه nlog n خواهد بود و نه n.
(۲۷ دى ۱۳۹۱ ۰۱:۰۸ ق.ظ)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 .
(۲۷ دى ۱۳۹۱ ۱۱:۰۸ ق.ظ)azad_ahmadi نوشته شده توسط: سلام . ممنون. نمی دونم چرا هنگ کرده بودم! بابت جواب اشتباه معذرت می خوام.این جواب هم زیاد مطمئن نیست،اما قابل بحثه.سلام.دشمنت شرمنده باشه آزادجان.
یک راه حل هم شاید به این صورت باشه که ابتدا مین هیپ رو تو یک آرایه قرار بدیم(این قسمت تو جواب نهایی تاثیر نداره!). سپس با جستجوی ترتیبی بزرگترین عنصر رو پیدا کنیم(که البته تو یکی از برگ ها است)، و با گره پیدا شده درخت ماکس هیپ رو ایجاد کنیم. صورت سوال گفته "ماکسیموم کردن تعداد مقایسه" یعنی بنظر به اصل این کاری نداره که کلا تبدیل مین هیپ به ماکس هیپ از چه مرتبه ایه، فقط تعداد بیشترین مقایسه ها رو می خواد. اینجا جستجوی ترتیبی n مقایسه و ایجاد درخت هیپ با n عنصر برابر n هست، و این دوتا بهم وابسته نیستن، n+n = 2n .
اول از همه بگم که میخوایم ماکس هیپ رو به مین هیپ تبدیل کنیم نه برعکس.(میدونم تاثیری نداره تو حل ولی برای اینکه هماهنگ باشیم میگم).
اما دقت کنید که آرایه مین هیپ که شما گفتید مرتب نیست، یعنی فقط بار اول که میخواهید جستجوی ترتیبی برای یافتن عنصر ماکزیمم انجام دهید، تعداد مقایسه ها n خواهد بود ولی برای پیدا کردن عناصربعدی n-1 وn-2 و....مقایسه لازمه.پس در کل بهn^2 مقایسه نیاز است و نه n.
اگر هم مثلا بخواهیم همان اول آرایه را مرتب کنیم بازهم زمان بیشتر از n لازمه
ممنون از دوستهای عزیز
جواب آلبالو جان که بنظر من درست وکامله
راجع به جواب این دوستمون من یه سوال واسم پیش اومد
چرا هزینه ساختن هیپ هم حساب کردین مگه ما هرمرحله جواب تو همون آرایه قرار نمیدیم؟
اگه اینجوری باشه که واسه جواب قبلی هم باید حساب کنیم
برای تبدیل max به min فکر کنم بشه o_n :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
---
عکسشم احتمالا o_n میشه
(۲۸ دى ۱۳۹۱ ۰۳:۵۳ ق.ظ)csharpisatechnology نوشته شده توسط: برای تبدیل max به min فکر کنم بشه o_n :توجه کنین که موضوعی که در لینک بالا مطرح کردین ارتباطی با سوال این تاپیک نداره، فقط انتخاب عنصر مینیمم از یک درخت مکس هیپ رو گفته(که (O (n میشه) نه تبدیل مکس هیپ به مین هیپ.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
---
عکسشم احتمالا o_n میشه
ولی ممنون بابت معرفی این سایت.
(۲۷ دى ۱۳۹۱ ۰۹:۲۱ ق.ظ)آلبالو نوشته شده توسط: از انتهای آرایه شروع کرده و بین هر سه عدد آخر،عنصر مینیمم را می یابیم که به ۲ مقایسه نیاز است.(سه گره اخر به این خاطر که یک پدر و دو فرزند میتوانیم داشته باشیم).در یک مکس هیپ عنصر مینیمم در یکی از برگ هاست (به تعداد n/2) نه لزوما سه تای آخر؛ مثلا جای ۱۹ رو با ۴۶ عوض و دوباره حل کنید؛
مینیمم را در اول آرایه minheap مینویسیم.
حال یک عنصر از آرایه maxheap کم شد(با دو مقایسه) و به آرایه minheap اضافه شد.همین پروسه را برای تمام عناصر تکرار میکنیم.n عنصر داریم و به ازای هرکدام نیاز به ۲ مقایسه هست؛ پس تعداد مقایسه ها(O (2n خواهد بود.
یک مثال:
maxheap: 98,96,53,83,43,46,35,19,47
(۲۸ دى ۱۳۹۱ ۰۸:۴۴ ب.ظ)Ghiasoddin نوشته شده توسط: در یک مکس هیپ عنصر مینیمم در یکی از برگ هاست (به تعداد n/2) نه لزوما سه تای آخر؛ مثلا جای ۱۹ رو با ۴۶ عوض و دوباره حل کنید؛ممنون.
عجب داستانی شده!!
ایده حل رو از مقسمی گرفته بودم.متاسفانه خیلی وقتا جواب مقسمی اشتباه هست و یا حتی با جواب سنجش هم هماهنگ نیست.
من کلید سنجش سال ۸۴ رو ندارم ولی با این اوصاف گزینه ۳ یا همون n logn محتمل تر به نظر میاد.
nlogn که مطمئنا هست فقط بهتر میشه یا نه. جای بحث داره. حالا کی میتونه ثابت کنه بهترم میشه؟!!
بنظرم مکس هیپ رابطه مستقیمی با مین هیپ نداره؛
بعبارتی، اینکه یه آرایه بدن و بگن مین هیپش کنید فرقی با حالتی که بدونیم آرایه ورودی مکس هیپه نداره؛
سریع ترین الگوریتم ساخت هیپ هم خطیه (در کتاب پوران الگوریتمش هست)؛ ایدش اینه که هر کدوم از n/2 (سقف) برگ به تنهایی خاصیت هیپ رو دارن؛ پس کافیه هر یک از گره های از n/2 (کف) تا گره ۱ رو یکبار heapify کنیم؛
مرتبش با یه رابطه بازگشتی تعریف میشه که فقط جوابشو یادمه که میشه اوی n (ممکنه ۲n جواب دقیقش باشه)؛
(۲۹ دى ۱۳۹۱ ۰۲:۵۵ ق.ظ)آلبالو نوشته شده توسط:(28 دى ۱۳۹۱ ۰۸:۴۴ ب.ظ)Ghiasoddin نوشته شده توسط: در یک مکس هیپ عنصر مینیمم در یکی از برگ هاست (به تعداد n/2) نه لزوما سه تای آخر؛ مثلا جای ۱۹ رو با ۴۶ عوض و دوباره حل کنید؛ممنون.
عجب داستانی شده!!
ایده حل رو از مقسمی گرفته بودم.متاسفانه خیلی وقتا جواب مقسمی اشتباه هست و یا حتی با جواب سنجش هم هماهنگ نیست.
من کلید سنجش سال ۸۴ رو ندارم ولی با این اوصاف گزینه ۳ یا همون n logn محتمل تر به نظر میاد.
جالبه بدونید ایده یوسفی هم همین بوده!!! وگفتن ۲n
ولی از اونجایی که دکتر قدسی هم گفتن ۲n پس درسته
من واسه حلش به این نتیجه رسیدم
اگر درختی داشته باشیم وبخوایم مینیمم هیپ کنیم۲مرحله داره
۱)چون واسه هر گره با فرزند چپ وراستش ۲مقایسه لازمه تا مینیمم بین آنها پیدا بشه پس به ازای زیردرخت شامل ۳گره ،۲مقایسه لازمه که این تعداد تقریبا برابر nمیشه
علاوه بر این تغییر و یافتن مینیمم در زیردرختهای بالاتر ممکنه باعث تغییر در زیردرختهای پایین تر بشه(که البته اگه زیر درخت چپ وراست داشته باشیم فقط در یکی از اونها تغییر داریم) واین تغییر تا ارتفاع اون زیر درخت ممکنه پیش بره
که اگه واسه یه درخت مثال بزنید یه چیزی نزدیک به n میشه
که در مجموع ۲n میشه (البته در بدترین حالت)
واسه این درخت که ۱۱ گره داره و۵زیر درخت
در مرحله اول۱۱ (nمقایسه
در مرحله دوم ۸تا
که مجموعا ۱۸ میشه و به ۲n نزدیکه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
فکر می کنم جواب این مسئله از طریق "هیپ درجا " یا" ساخت هیپ به روش جوان ترین پدر "باشه .
که اصطلاح ساخت هیپ به روش جوان ترین پدر در کتاب آقای مقسمی اومده و ص ۲۵۷ توضیح دادن.
و اصطلاح "هیپ درجا " در کتاب آقای قدسی اومده و در ص۳۳۷ اثبات شده که از مرتبه (O(n هست.
الگوریتم:
BuildHeap(A
for (i=[lengthA downto 1
do MaxHeapify(A,i
که نحوه کار( MaxHeapify(A,i هم ص۲۴۲ آقای قدسی اومده و به این صورت هست که ابتدا اندیس بزرگترین فرزند i یا( bigchild(i رو به دست میاریم اگر کلید i از کلیدbigchildکمتر نباشد کار به اتمام رسیده ولی اگر کلید i از کلید bigchild کمتر باشد در ان صورت این دو کلید را با هم عوض می کنیم و با فراخوانی MaxHeapify(A, bigchild از اندیس bigchild تا آخر آرایه را به صورت هرم در می آوریم.
(۲۷ دى ۱۳۹۱ ۰۹:۲۱ ق.ظ)آلبالو نوشته شده توسط:(27 دى ۱۳۹۱ ۰۲:۰۳ ق.ظ)azad_ahmadi نوشته شده توسط: سلام.سلام
فکر می کنم به این صورت باشه که هربار یک حذف از مین هیپ داشته باشه(توجه داشته باش که بعد از اون باید تابع heapify فراخوانی بشه تا دوباره مین هیپ رو تازه سازی کنه که هزینه اون O(n هست)، و از عنصر حذف شده یک ماکس هیپ بسازه، که هزینه ساخت یک هیپ هم برابر هست با O(n . درکل میشه ۲n که از مرتبه O(n هست.
موفق باشید.
دقت کنید که درج و حذف در heap از مرتبه log n هست و بنابراین ساخت یک هیپ از مرتبه nlog n خواهد بود و نه n.
(۲۷ دى ۱۳۹۱ ۰۱:۰۸ ق.ظ)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