اگر در یک max-heapحاوی اعداد متمایز ۱ تا ۱۲۸ باشد حداکثر۲۲ عدد بیشتر از ۱۰۰ می تواند در پایین ترین سطح قرار گیرد.
چرا درسته؟؟
(۲۲ بهمن ۱۳۹۲ ۱۱:۲۰ ق.ظ)ماهسان لیما نوشته شده توسط: اگر در یک max-heapحاوی اعداد متمایز ۱ تا ۱۲۸ باشد حداکثر۲۲ عدد بیشتر از ۱۰۰ می تواند در پایین ترین سطح قرار گیرد.
چرا درسته؟؟
تو این max-heap دقیقا یه عنصر تو پایین ترین سطح داریم. حالا برای اعداد بزرگتر از ۱۰۰ بررسی می کنیم.اگر شاخه ی سمت چپ رو با بزرگترین عدد ها پر کنیم(اولی ۱۲۸، دومی ۱۲۷ ، چهارمی ۱۲۶ ، ...) تا قبل از عنصر مورد نظر ۱۲۲ تا ۱۲۸ رو توی درخت گذاشتیم.پس می تونیم ۱۲۱ تا ۱۰۱ رو توی عنصر آخر بذاریم که می شه ۲۱ تا . اگر خود ۱۰۰ رو هم حساب کنیم می شه ۲۲ تا.
در حالت کلی وقتی با اعداد ۱ تا [tex]2^n[/tex] یه heap می سازیم n-lgn تا از این عددا می تونن توی سطح آخر قرار بگیرن.