Нижний грани на куче?

Question

Хорошо известно, что наихудшее время выполнения для Heapsort-ω (n lg n), но у меня проблемы с тем, почему это так. В частности, первый шаг Heapsort (создающий макс-HEAP) занимает время θ (n). Затем за ним следует делеции N. Я понимаю, почему каждое удаление кучи требует времени O (LG N); Резлакация куча включает в себя операцию пузырьков, которая занимает время O (h) на высоте кучи, а H = O (Lg n). Однако я не вижу, почему этот второй шаг должен сделать ω (n lg n). Кажется, что любая отдельная куча не обязательно приведет к тому, что узел перемещается на вершину, чтобы пузырь, все вниз по дереву.

Мой вопрос: кто-нибудь знает о хорошем нижнем доказательстве для наилучшего поведения Heapsort?

Answer 1

Так что я немного копал себя, и похоже, что этот результат на самом деле довольно недавно! Первое нижнее доказательство, которое я могу найти,-это 1992 год, хотя сам Heapsort был изобретен в 1964 году.

Формальное нижнее доказательство связано с тем, что «Анализ Heapsort» Шаффера и Седжвика «Heapsort». Вот немного перефразированная версия доказательства, которая пропускает некоторые технические детали.

Для начала давайте предположим, что n = 2^k - 1 для некоторых K, что гарантирует, что у нас есть полная бинарная куча. Я покажу, как справиться с этим делом отдельно позже. Потому что у нас есть 2^k - 1 элементы, первый проход Heapsort, в θ (n), создаст кучу высоты k. Теперь рассмотрим первую половину Dequeues из этой кучи, которая удаляет 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. Даже в лучшем случае это означает, что должно быть как минимум 2^K-3 + 1 большие узлы на уровне K - 2, что означает, что будет не менее 2^K-4 + 1 большие узлы на уровне K - 3 и т. Д. Суммируя все эти узлы, мы понимаем, что есть 2^k-2 + 2^K-3 + 2^K-4 + ... + 2⁰ + k большие узлы. Но это значение строго больше 2^k-1, противоречит тому факту, что мы работаем только 2^k-1 узлы здесь.

Хорошо ... теперь мы знаем, что есть не более 2^k-2 Большие узлы в нижнем слое. Это означает, что должно быть не менее 2^k-2 из больших узлов в первых слоях К-2. Теперь мы спрашиваем - какова сумма над всеми этими узлами расстояния от этого узла до корня? Ну, если у нас есть 2^k-2 узлы расположены где -то в полной куче, затем не более 2^K-3 из них могут быть на первых уровнях K - 3, и поэтому есть как минимум 2^k-2 - 2^K-3 = 2^K-3 Тяжелые узлы на уровне k - 2. Следовательно, общее количество изменений, которые необходимо выполнить, по крайней мере (k - 2) 2^K-3. Анкет Поскольку n = 2^k-1, k = θ (lg n), и поэтому это значение составляет θ (n lg n) по мере необходимости.

Answer 2

Простой наблюдение Ответ заключается в следующем: элементы в куче:

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

Например, если у вас есть 7 пунктов:

1
2
4

И если у вас есть 8 пунктов:

1
2
4
1

Есть 2 разных дерева кучи, сначала, по крайней мере, N/4 - 1 элементы кучи находятся на последнем уровне или нет, так что есть, по крайней мере, есть n/4 - 1 предмет на уровне до последнего, в первом случае это требуется O((n/4 - 1) * log(n/2)) Чтобы удалить элементы последнего уровня из кучи, а во втором случае это требуется O((n/4 - 1) * log(n/4)) удалить элементы с до последнего уровня. Таким образом, в обоих случаях требуется ω (n log (n)) только для элементов N/4 - 1, так что это нижняя граница (легко может сказать, что она плотная нижняя граница).

Answer 3

Вот решение, которое использует термины CLR:
Мы начинаем с максимума, который является полным бинарным деревом с n элементы.
Можно сказать, что в полном бинарне есть n/2 листья и n/2 Внутренние узлы.
n/2 итерации HEAP-SORT Удалите самый большой n/2 Элементы из кучи.
Позволять S быть набором самых больших n/2 элементы.
Может быть больше всего n/4 Элементы от S в листьях, так как должно быть дополнительное n/4 из них во внутренних узлах.
Позволять L будь это n/4 крупнейшие элементы от S которые в листьях.
Так что если есть n/4 Элементы от S на уровне 0 (уровень листьев), тогда должно быть, по крайней мере, n/8 из них на уровне 1.
Позволять P будь это n/8 Элементы от S которые находятся на уровне 1.
n/2 итерации кучи могут дать элементы из L короткий сокращение до корня, а затем из кучи, но элементы из P Должен пройти до корня, прежде чем они будут удалены из кучи.
Так что есть хотя бы (n/8)(lgn-1) операции, которые дают нам время выполнения ω (nlgn).
Теперь для случая максимального HEAP, который не имеет всех листьев на уровне 0.
Позволять k быть количеством его листьев на уровне 0.
После k Итерации кучи, у нас остается максимальный гип, который является полным бинарным деревом с высотой lgn-1.
Мы можем продолжить наши доказательства так же.
Теперь для случая, когда их меньше n/4 листья от S.
Позволять k быть количеством элементов из S которые находятся в листьях на уровне 0.
Если k <= n/8 тогда должно быть хотя бы n/8 Элементы от S на уровне 1.
Это потому, что может быть в общей сложности n/4 Элементы выше уровня 1.
Мы продолжаем доказательство так же.
Если k>n/8 тогда должно быть хотя бы n/16 Элементы от S которые находятся на уровне 1.
Мы продолжаем доказательство так же.
Мы пришли к выводу, что время выполнения кучи составляет ω (nlgn).