تشخیص بزرگترین عدد در آخرین سطح هیپ - نسخه‌ی قابل چاپ

تشخیص بزرگترین عدد در آخرین سطح هیپ - m@hboobe - 26 مهر ۱۳۹۱ ۰۷:۰۵ ب.ظ [attachment=7257] جوابش با مثال به نتیجه رسیده بود [attachment=7258] چطوری اومده ۸ و ۷ و ۶ و ۵ رو اینجور پشت سر هم آورده؟؟!!

تشخیص بزرگترین عدد در آخرین سطح هیپ - azad_ahmadi - 26 مهر ۱۳۹۱ ۱۱:۴۳ ب.ظ این سوال، سوال کنکور امسال هم بود(ساختمان داده ها-مهندسی کامپیوتر) . ببین ماکس هیپ یعنی پدر از فرزندانش بزرگتر باشه. حالا بزرگترین عدد که همون ۶۴ باشه رو ریشه قرار میدیم. توجه کن که گفته "ماکزیموم عددی که تو ریشه باشه"، پس ۶۳ رو فرزند چپ ریشه قرار میدیم. به این نکته هم توجه کن که هیپ باید درخت کامل باشه (یعنی از چپ به راست کامل بشه نودهایی که داره). سمت راست ریشه رو کاری نداریم چون بزرگترین فرزند برامون مهمه. ۶۲ رو زیر ۶۳ قرار میدیم(بعنوان فرزند چپ). همین منوال رو ادامه میدیم. توجه کن که ارتفاع درخت برابر با logn +1 خواهد بود(البته لگاریتم رو باید سطح پایینش رو در نظر بگیریم). درخت رو وقتی کامل کنی می بینی که فقط یک نود اضافه داره که آخرین فرزند چپ آخرین نود است. که برابر ۵۸ خواهد بود. ۶۴ -----۶۳ ----------۶۲ ----------------۶۱ ---------------------۶۰ --------------------------۵۹ -----این قسمت خالی است و دیگر نودی وجود ندارد---------۵۸ پس آخرین نود میشه ۵۸ ، که ماکزیموم است.