Двоичная куча: доказательство сложности построения О(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;

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

Лемма.

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

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

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

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

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


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



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



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





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