algorithm - ヒープ内の反転の最悪のケースの数が Ω(nlogn) であることを証明する方法は?

Question

私は試験の準備で忙しく、古い試験問題をやっているだけです。以下の質問は、私ができないように見える唯一のものです (どこから始めればよいかわかりません)。どんな助けでも大歓迎です。

Ω(nlogn) 比較ソート境界、ボトムアップ ヒープ構築の theta(n) 境界、および挿入ソートの順序複雑度を使用して、ヒープ内の反転の最悪のケースの数が Ω(nlogn) であることを示します。

Answer 1

挿入ソートの複雑さはO（n + d）です。ここで、dは反転ペアの数です。

ここで、一連の数値があり、それをヒープ化して（Theta（n））、それらに対して挿入ソートを実行するとします。ヒープ配列の反転ペアのワーストケース数についてはどうでしょうか。