Алгоритм SiftDown Количество сравнений

Question

Я недавно работал с алгоритмом siftDown, используемым для построения двоичных куч. В книге «Алгоритмы и структуры данных: базовая панель инструментов» в упражнении 6.5 указано, что для данной реализации этого алгоритма необходимы сравнения элементов 2*log(n). Теперь я попытался понять, почему это так, но я не мог. Почему это правильно?

Answer 1

При вызове siftDown(i) сначала выполнить два элемента сравнения:

• Первый находится между h[2i] и h[2i+1].
• Второй период находится между h[i] и h[m].

После выполнения двух сравнений вы рекурсивный вызов siftDown(m) где m=2i или m=2i+1. То есть, каждый вызов siftDown() с кучей элементов n приводит к получению двух элементов сравнения и вызову siftDown() с кучей элементов n/2.

Поэтому T(n) число сравнений при вызове siftDown() с n -элементной кучей, удовлетворяет:

T(n) = 2 + T(n/2) 

Решение этого рекуррентного соотношения

T(n) = 2logn 

Вы можете видеть, что вышеуказанное соотношение решает до 2logn, наблюдая, что каждый раз выполняется ровно 2 элементарных сравнения, а число раз равно logn (потому что если вы начинаете с n и продолжаете делиться на 2 снова и снова, вы делаете это после logn делений).

Следовательно, общее количество сравнений элементов, составленное siftDown(), составляет около 2logn.