دوستان عزیز؛
با سوالی در مورد هیپ ها مواجه شدم که می خواست مقادیر گره هایی که می توانند در آخرین سطح درخت قرار بگیرند رو بیابم، من سوال رو همراه با پاسخ در قالب همین پست برایتان پیوست کرده ام، لطفا در صورت امکان راهنمایی نمایید.
امیدوارم تصویر ضمیمه به شما کمک کند در این تصویر عکس درخت heap مورد سوال رسم شده فقط شاخه های مهم را نشان دادم و بقیه شاخه های غیر مهم نقطه چین شدند شکل اصلی این درخت به این صورت که یک درخت پر به ارتفاع ۶(ارتفاع ریشه ۱ در نظر گرفته شده) در نظر بگیرید و به سمت چپ ترین برگ ان یک نود اضافه کنید که مقدار این نود حداکثر ۵۸ می باشد
(۰۱ مهر ۱۳۹۲ ۰۹:۱۱ ب.ظ)poldasht نوشته شده توسط: دوستان عزیز؛
با سوالی در مورد هیپ ها مواجه شدم که می خواست مقادیر گره هایی که می توانند در آخرین سطح درخت قرار بگیرند رو بیابم، من سوال رو همراه با پاسخ در قالب همین پست برایتان پیوست کرده ام، لطفا در صورت امکان راهنمایی نمایید.
یه نکته وجود داره و اون این است که توی یک هرم بیشینه k امین بزرگترین عنصر در سطح بیشتر از k نمیتونه قرار بگیره(اگه بره توی سطح k + 1 دیگه k امین نیست !)، حالا ما میخواهیم بدونیم بزرگترین عددی که میتونه توی سطح آخر قرار بگیره چیه؟ میدونیم که ارتفاع یک هرم برابر [tex]\lfloor lg(n) \rfloor$[/tex] هتش که واسه سوال ما این میشه ۶، پس توی برگ کسی میتونه قرار بگیره که (که یدونه هم هست) که از ۶ تا عنصر دیگه کوچک تر باشه، که بزرگترین عددی که از ۶ تا عدد دیگه کوچکتره میشه ۵۸ که از اعداد ۶۴ و ۶۳ و۶۲ و۶۱ و۶۰ و ۵۹ کوچکتر هست.
واقعا دسستون درد نکنه، کاملا متوجه مسئله شدم. درود بر شما ها.
فقط محض اطلاع دیگر دوستان، عمق یک درخت دودویی کامل مثل همین هیپ [tex]\left \lfloor logn \right \rfloor 1[/tex] هستش، چون ظاهرا غلط املایی شده بود، گفتم اگه یادآوری کنم شاید بهتر باشه.
باز هم بابت لطفطون سپاسگذارم عزیزان.