Так что я немного покопался, и похоже, что этот результат на самом деле довольно недавний! Первое доказательство нижней границы, которое я могу найти, относится к 1992 году, хотя сам гиппорт был изобретен в 1964 году.
Формальное нижнее доказательство связано с работой Шаффера и Седжвика "Анализ Heapsort". Вот слегка перефразированная версия доказательства, в которой пропущены некоторые технические детали.
Для начала предположим, что n = 2 k - 1 для некоторого k, что гарантирует, что у нас полная двоичная куча. Я покажу, как обращаться с этим делом отдельно позже. Поскольку у нас 2 k - 1 элементов, первый проход heapsort в & Theta; (n) создаст кучу высоты k. Теперь рассмотрим первую половину очереди из этой кучи, которая удаляет из кучи 2 k-1 узлов. Первое ключевое наблюдение заключается в том, что если вы берете начальную кучу, а затем отмечаете здесь все узлы, которые на самом деле в конечном итоге становятся заблокированными, они образуют поддерево кучи (т. Е. У каждого обрабатываемого узла есть родительский объект, который также освобождается от очереди). Вы можете видеть это, потому что если бы это было не так, то был бы какой-то узел, родительский элемент которого (большего размера) не был удален из очереди, хотя сам узел был снят, что означает, что значения вышли из строя.
Теперь рассмотрим, как узлы этого дерева распределяются по куче. Если вы пометите уровни кучи 0, 1, 2, ..., k - 1, то будет некоторое количество этих узлов на уровнях 0, 1, 2, ..., k - 2 (то есть все, кроме нижнего уровня дерева). Для того, чтобы эти узлы были выведены из кучи, их нужно поменять местами до корня и поменять местами только на один уровень за раз. Это означает, что одним из способов нижнего ограничения времени выполнения heapsort является подсчет количества перестановок, необходимых для передачи всех этих значений в корень. На самом деле, это именно то, что мы собираемся сделать.
Первый вопрос, на который нам нужно ответить, - сколько самых больших 2 k-1 узлов не находятся на нижнем уровне кучи? Мы можем показать, что это не больше, чем 2 k-2 в силу противоречия. Предположим, что на нижнем уровне кучи имеется не менее 2 k-2 + 1 из самых больших узлов. Тогда каждый из родителей этих узлов также должен быть большими узлами на уровне k - 2. Даже в лучшем случае это означает, что на уровне k должно быть не менее 2 k-3 + 1 больших узлов. - 2, что означает, что на уровне k - 3 будет по крайней мере 2 k-4 + 1 больших узлов и т. Д. Суммируя по всем этим узлам, мы получаем, что существует 2 k-2 + 2 k-3 + 2 k-4 + ... + 2 0 + k больших узлов. Но это значение строго больше, чем 2 k-1 , что противоречит тому факту, что мы работаем только с 2 k-1 узлами.
Хорошо ... теперь мы знаем, что в нижнем слое есть не более 2 k-2 больших узлов. Это означает, что в первых слоях k-2 должно быть не менее 2 k-2 больших узлов. Теперь мы спросим - какова сумма расстояний от этого узла до корня по всем этим узлам? Итак, если у нас есть 2 k-2 узлов, расположенных где-то в полной куче, то самое большее 2 k-3 из них может быть на первых k - 3 уровнях На уровне k - 2 должно быть не менее 2 k-2 - 2 k-3 = 2 k-3 тяжелых узлов. Следовательно, общее количество Свопы, которые необходимо выполнить, составляют не менее (k - 2) 2 k-3 . Поскольку n = 2 k -1, k = & Theta; (lg n), и поэтому это значение равно & Theta; (n lg n), как требуется.