CLRS 、第3版、 155ページでは、MAX-HEAPIFYでは、
"the worst case occurs when the bottom level of the tree is exactly half full"
その理由は、この場合、Max-Heapifyが左側のサブツリーを「フロートダウン」する必要があるためだと思います。
しかし、私が得ることができなかったのは、「なぜ半分いっぱい」なのか？
Max-Heapifyは、左側のサブツリーにリーフが1つしかない場合にも、フロートダウンする可能性があります。では、これを最悪のケースと考えてみませんか？
コンテキスト全体を読む：
子のサブツリーのサイズはそれぞれ最大2n/3です。最悪のケースは、ツリーの最後の行がちょうど半分いっぱいになったときに発生します。
実行時間T(n)はツリー内の要素の数（）によって分析されn、再帰はサブツリーの1つにステップインするため、サブツリー内のノード数の上限を見つける必要があります。これにより、次のようになりnます。それT(n) = T(max num. nodes in subtree) + O(1)
サブツリー内のノード数の最悪のケースは、最終行が一方の側で可能な限りいっぱいになり、もう一方の側で可能な限り空になる場合です。これはハーフフルと呼ばれます。また、左側のサブツリーのサイズは。で囲まれ2n/3ます。
少数のノードのみでケースを提案している場合、すべての基本ケースを考慮O(1)して無視できるため、それは関係ありません。