В CLRS, третье издание, на стр. 155, указано, что в MAX-HEAPIFY,
"the worst case occurs when the bottom level of the tree is exactly half full"
Я думаю, причина в том, что в этом случае Max-Heapify должен "плавать вниз" через левое поддерево.
Но то, чего я не мог получить, - "почему половина полна"?
Max-Heapify также может плавать, если левое поддерево имеет только один лист. Так почему бы не считать это худшим случаем?
Прочитайте весь контекст:
Поддеревья для детей имеют размер не более 2n/3 - худший случай возникает, когда последняя строка дерева ровно наполовину полна
Поскольку время выполнения T(n) анализируется количеством элементов в дереве (n), а шаги рекурсии - в одно из поддеревьев, нам нужно найти верхнюю оценку числа узлов в поддерево, относительно n, и это даст, что T(n) = T(max num. nodes in subtree) + O(1)
Наихудший случай числа узлов в поддереве - это когда последняя строка максимально полна с одной стороны и как можно более пустая с другой. Это называется наполовину полным. И размер левого поддерева будет ограничен 2n/3.
Если вы предлагаете случай с несколькими узлами, то это не имеет значения, так как все базовые случаи можно считать O(1) и игнорировать.