algorithm - 如何证明堆中最坏情况的反转数是Ω（nlogn）？

Question

我正忙着准备考试，只是在做一些旧试卷。下面的问题是唯一一个我似乎做不到的问题（我真的不知道从哪里开始）。任何帮助将不胜感激。

使用 Ω(nlogn) 比较排序界限、自底向上堆构造的 theta(n) 界限和插入排序的顺序复杂度来表明堆中最坏情况的反转数是 Ω(nlogn)。

Answer 1

插入排序的复杂度是 O(n+d)，其中 d 是反转对的数量。

现在假设您有一组数字，您将其堆化 (Theta(n))，然后对它们执行插入排序。它对堆数组中最坏情况下的反转对数量有什么看法？