Докажите, что максимальное сравнение двоичной кучи составляет (2N-2)

Я пытаюсь доказать, что для двоичных куч, buildHeap делает не более (2N-2) сравнения между элементами. Мне очень трудно доказать это утверждение.

Источник

1 ответ

Алгоритм сборки-кучи запускается в средней точке и перемещает элементы по мере необходимости. Давайте рассмотрим кучу из 127 предметов (7 уровней). В худшем случае:

64 nodes (the leaf level) don't move at all
32 nodes move down one level
16 nodes move down two levels
 8 nodes move down three levels
 4 nodes move down four levels
 2 nodes move down five levels
 1 node moves down six levels

Так что в худшем случае у вас есть

64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6
0 + 32 + 32 + 24 + 16 + 10 + 6 = 120 swaps

Так что в худшем случае build-heap делает меньше, чем N перестановок.

Поскольку в build-heap требуется поменять элемент с наименьшим из его дочерних элементов, для запуска подкачки требуется два сравнения: одно для нахождения наименьшего из двух дочерних элементов и одно для определения, является ли узел больше и его необходимо заменить.

Количество сравнений, необходимых для перемещения узла: 2*(levels_moved+1)и не более N/2 узлов будут перемещены.

Общий случай

Нам нужно доказать, что максимальное количество сравнений не более 2N-2. Как я отмечал выше, для перемещения узла на один уровень требуется два сравнения. Таким образом, если количество перемещенных уровней меньше N (то есть (N-1) или меньше), то максимальное количество сравнений не может превышать 2N-2.

Я использую полную кучу в обсуждении ниже, потому что это представляет худший случай.

В полной куче из N элементов есть (N+1)/2 узла на уровне листа. (N+1)/4 на следующем уровне вверх. (N+1)/8 на следующем и т. Д. В итоге вы получите следующее:

(N+1)/2 nodes move 0 levels
(N+1)/4 nodes move 1 level
(N+1)/8 nodes move 2 levels
(N+1)/16 nodes move 3 levels
(N+1)/32 nodes move 4 levels
...

Это дает нам серию:

((N+1)/2)*0 + ((N+1)/4)*1 + ((N+1)/8)*2 + ((N+1)/16)*3 ...

Давайте посмотрим, что это делает для куч разных размеров:

heap size  levels   levels moved
   1         1          0
   3         2          1
   7         3          2*1 + 1*2 = 4
   15        4          4*1 + 2*2 + 1*3 = 11
   31        5          8*1 + 4*2 + 2*3 + 1*4 = 26
   63        6          16*1 + 8*2 + 4*3 + 2*4 + 1*5 = 57
   127       7          32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120
         ....

Я запустил это для кучи до 20 уровней (размер миллион и изменение), и это справедливо: максимальное количество уровней, перемещаемых для полной кучи из N элементов, равно N-log2(N+1).

К сожалению, у меня нет математической подготовки, чтобы написать формальное доказательство. Возможно, кто-то еще может помочь.

Источник
Другие вопросы по тегам