Алгоритм 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,