В CLRS , третье издание, на странице 155, предполагается, что в MAX-HEAPIFY
"the worst case occurs when the bottom level of the tree is exactly half full"
, я полагаю, причина в том, что в этом случае Max-Heapify должен «плавать вниз» через левое поддерево.
Но я не мог понять, «почему наполовину заполнен»?
Max-Heapify также может плавать вниз, если левое поддерево имеет только один лист. Так почему бы не считать это наихудшим случаем?