Двоичная Куча: Доказательство Сложности Конструкции O(N)

На самом деле мы поговорим о двоичная куча и его построение с помощью Sift-Down (или Heapify).

Многие наверняка знают, что построение кучи таким способом осуществляется в

Двоичная куча: доказательство сложности конструкции O(n)

.

Здесь я приведу доказательство этого факта.

Вот пример процедуры построения кучи из массива в Паскале.

   

 procedure siftdown(v:longint);
 var
   min,l,r:longint;
 begin
   l:=v*2; r:=v*2+1;
   min:=v;
   if (l <= s) and (a[l] < a[min]) then min:=l;
   if (r <= s) and (a[r] < a[min]) then min:=r;
   if min <> v then begin
     swap(a[min], a[v]);
     sift_down(min);
   end;
 end;
 
 procedure build;
 var
   i:longint;
 begin
   for i:=n downto 1 do siftdown(i);
 end;

Итак, дан массив, состоящий из

Двоичная куча: доказательство сложности конструкции O(n)

элементы и

Двоичная куча: доказательство сложности конструкции O(n)

количество звонков оператора

Двоичная куча: доказательство сложности конструкции O(n)

(в процедуре

Двоичная куча: доказательство сложности конструкции O(n)

) при построении кучи с использованием этого массива.

Очевидно,

Двоичная куча: доказательство сложности конструкции O(n)

определяет время выполнения процедуры

, что нам интересно.

Лемма.

Пусть для некоторого элемента массива при вызове

Двоичная куча: доказательство сложности конструкции O(n)

было сделано

звонки оператора

.

Тогда его показатель не превышал

Двоичная куча: доказательство сложности конструкции O(n)

.

Доказательство: В

Двоичная куча: доказательство сложности конструкции O(n)

звонки оператора

индекс

элемент увеличивается как минимум

один раз.

Пусть это сейчас

Двоичная куча: доказательство сложности конструкции O(n)

, т.е.

Двоичная куча: доказательство сложности конструкции O(n)

.

Затем после

Двоичная куча: доказательство сложности конструкции O(n)

у нас есть проблемы

, что невозможно, так как в нашей куче

элементы.

Двоичная куча: доказательство сложности конструкции O(n)

Оценим теперь сверху величину

.

Пусть элемент массива имеет индекс

Двоичная куча: доказательство сложности конструкции O(n)

.

Будет

Двоичная куча: доказательство сложности конструкции O(n)

, такой, что

.

Тогда для того, чтобы элемент массива с индексом

Двоичная куча: доказательство сложности конструкции O(n)

встал на место в куче, больше не потребуется

звонки

(по лемме).

Количество элементов с такими индексами есть величина

Двоичная куча: доказательство сложности конструкции O(n)

, который в

уходит в ноль.

Таким образом,

Двоичная куча: доказательство сложности конструкции O(n)

В

члены равны нулю (поэтому цикл в процедуре

ты можешь начать с

).

Оценим левый множитель в каждом слагаемом суммы как

Двоичная куча: доказательство сложности конструкции O(n)

Отсюда мы имеем:

Давайте оценим каждую из сумм.