Pull to refresh

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

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

Вот пример процедуры построения кучи по массиву на языке 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;


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

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

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

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

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

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

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

image

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

image

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

image

image

Таким образом, image.
image ограничена сверху функцией, которая есть image. Значит, image.
Следовательно, время работы процедуры image есть величина пропорциональная image.
Tags:
Hubs:
Total votes 41: ↑25 and ↓16+9
Comments3

Articles