Как доказать в худшем случае число инверсий в куче Ω (nlogn)?

Question

Я занят подготовкой к экзаменам, просто делаю старые экзаменационные работы. Вопрос ниже - единственный, который я, кажется, не могу сделать (я действительно не знаю, с чего начать). Любая помощь будет принята с благодарностью.

Используйте границу сортировки сравнения Ω (nlogn), границу тета (n) для построения кучи снизу вверх и сложность порядка сортировки вставок, чтобы показать, что наихудшее число инверсий в куче равно Ω (nlogn ).

Answer 1

Сложность вставки сортировки - O (n + d), где d - количество пар инверсии.

Теперь скажите, что у вас есть набор чисел, который вы складываете в кучу (Theta (n)), а затемвыполнить вставку сортировки на них.Что это говорит о наихудшем числе пар инверсий в массиве кучи?