Пытаюсь понять max heapify

Вот что делает MAX-HEAPIFY:

Учитывая узел с индексом i, чьи левое и правое поддеревья являются максимальными кучами, MAX-HEAPIFY перемещает узел с индексом i вниз по максимальной куче до тех пор, пока он не перестанет нарушать максимальное значение. -heap свойство (то есть узел не меньше своих дочерних элементов).

Самый длинный путь, который может пройти узел, прежде чем он окажется в правильном положении, равен начальной высоте узла. Каждый раз, когда узлу нужно спуститься еще на один уровень в дереве, алгоритм выберет ровно одну ветвь и никогда не вернется назад. Если узел, к которому добавляется куча, является корнем максимальной кучи, то самый длинный путь, который он может пройти, равен высоте дерева или O(log n).

MAX-HEAPIFY перемещает только один узел. Если вы хотите преобразовать массив в максимальную кучу, вы должны убедиться, что все поддеревья имеют максимальную кучу, прежде чем переходить к корню. Вы делаете это, вызывая MAX-HEAPIFY на n/2 узлах (листья всегда удовлетворяют свойству max-heap).

Из КЛРС:

for i = floor(length(A)/2) downto 1
   do MAX-HEAPIFY(A,i)

Поскольку вы вызываете MAX-HEAPIFY O(n) раза, построение всей кучи занимает O(n log n).*

_{* Как упоминалось в комментариях, можно показать более точную верхнюю границу O(n). Анализ см. в разделе 6.3 2-го и 3-го изданий CLRS. . (Мое первое издание упаковано, поэтому я не смог проверить номер раздела.)}

В худшем случае не придется ли реверсировать каждый отдельный узел?

Вам не нужно проходить через каждый узел. Стандартный алгоритм max-heapify: (взято из Википедии)

Max-Heapify (A, i):
    left ← 2*i  // ← means "assignment"
    right ← 2*i + 1
    largest ← i

    if left ≤ heap_length[A] and A[left] > A[largest] then:
        largest ← left
    if right ≤ heap_length[A] and A[right] > A[largest] then:
        largest ← right

    if largest ≠ i then:
        swap A[i] and A[largest]
    Max-Heapify(A, largest)

Вы можете видеть, что при каждом рекурсивном вызове вы либо останавливаетесь, либо продолжаете работу с поддеревом left или right. В последнем случае вы уменьшаете высоту дерева с помощью 1. Поскольку дерево кучи сбалансировано по определению, вы должны сделать не более log(N) шагов.

Вот аргумент, почему это O (N).

Предположим, что это полная куча, поэтому у каждого нелистового узла есть два потомка. (Это все еще работает, даже если это не так, но это больше раздражает.)

Положите монету на каждый узел дерева. Каждый раз, когда мы делаем обмен, мы собираемся потратить одну из этих монет. (Обратите внимание, что когда элементы меняются местами в куче, монеты не меняются местами с ними.) Если мы запустим MAX-HEAPIFY и останутся монеты, это означает, что мы сделали меньше свопов, чем узлов в дереве. и, таким образом, MAX-HEAPIFY выполняет O(N) свопов.

Утверждение: после завершения работы MAX-HEAPIFY в куче всегда будет хотя бы один путь от корня к листу с монетами на каждом узле пути.

Доказательство по индукции: для кучи с одним узлом нам не нужно делать никаких обменов, поэтому нам не нужно тратить монеты. Таким образом, один узел сохраняет свою монету, и у нас есть полный путь от корня до листа (длиной 1) с целой монетой.

Теперь предположим, что у нас есть куча с левой и правой подкучами, и MAX-HEAPIFY уже выполняется на обеих. Согласно индуктивной гипотезе, у каждого есть хотя бы один путь от корня к листу с монетами на нем, поэтому у нас есть как минимум два пути от корня к листу с монетами, по одному для каждого потомка. Самое большее, что нужно будет пройти корню, чтобы установить свойство MAX-HEAP, — это переместиться до конца дерева. Допустим, он переключается вниз в левое поддерево и переключается полностью вниз. Для каждого обмена нам нужно тратить монету, поэтому мы тратим ее с узла, на который перешел корень.

При этом мы потратили все монеты на один путь от корня к листу, но помните, что изначально у нас было как минимум два! Таким образом, у нас все еще есть путь от корня к листу с монетами после того, как MAX-HEAPIFY запустит всю кучу. Следовательно, MAX-HEAPIFY потратил меньше монет, чем узлов в дереве. Следовательно, количество свопов равно O(N). КЭД.