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

Собственно речь пойдет о двоичной куче и ее построении с помощью Sift-Down(или Heapify). Многим наверное известно, что построение кучи таким образом осуществляется за . Здесь я приведу доказательство этого факта.

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

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; 

Итак, пусть дан массив, состоящий из элементов, и количество вызовов оператора (в процедуре ) при построении кучи по этому массиву. Очевидно, определяет время работы процедуры , которое нам и интересно.

Лемма.

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

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

При вызовах оператора индекс элемента возрастает как минимум в раз. Пусть теперь , т.е. . Тогда после вызовов имеем , что невозможно, так как в нашей куче элементов.

Оценим теперь сверху величину . Пусть элемент массива имеет индекс . Найдется , такое что . Тогда для того, чтобы элемент массива с индексом встал на свое место в куче потребуется не больше вызовов (по лемме). Количество элементов с такими индексами есть величина , которая при обращается в нуль.

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

При слагаемые нулевые(поэтому цикл в процедуре можно начинать с ).
Оценим левый множитель в каждом слагаемом суммы, как

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

Оценим каждую из сумм.

Таким образом, .
ограничена сверху и снизу функциями, которые есть . Значит, .
Следовательно, время работы процедуры есть величина пропорциональная .