наихудший случай в MAX-HEAPIFY: «наихудший случай возникает, когда нижний уровень дерева заполнен ровно наполовину»

В CLRS , третье издание, на странице 155, предполагается, что в MAX-HEAPIFY

"the worst case occurs when the bottom level of the tree is exactly half full"  

, я полагаю, причина в том, что в этом случае Max-Heapify должен «плавать вниз» через левое поддерево.
Но я не мог понять, «почему наполовину заполнен»?
Max-Heapify также может плавать вниз, если левое поддерево имеет только один лист. Так почему бы не считать это наихудшим случаем?

15
задан 1 0 12 July 2016 в 09:49
поделиться