Процедура max-heapify при сортировке кучи требует времени, которое можно проанализировать с помощью различных методов. Вот некоторые часто используемые подходы:

1. Рекурсивный анализ. Временную сложность max-heapify можно проанализировать с помощью рекурсивного подхода. В худшем случае процедура выполняет два рекурсивных вызова для поддерева размера n/2, где n — общее количество элементов в куче. Следовательно, временная сложность может быть выражена как T(n) = 2T(n/2) + O(1), что приводит к временной сложности O(log n).

2. Анализ свойств кучи: Max-heapify гарантирует, что свойство кучи поддерживается в структуре данных максимальной кучи. Анализируя количество сравнений и замен, выполненных во время процедуры, мы можем оценить ее временную сложность. В худшем случае процедуре может потребоваться несколько раз поменять местами корневой элемент с одним из его дочерних элементов, пока свойство кучи не будет удовлетворено. Для этого требуется ряд сравнений и замен, пропорциональных высоте кучи, которая равна O(log n).

3. Анализ двоичного дерева. Процедуру max-heapify также можно проанализировать, рассматривая базовое представление кучи в виде двоичного дерева. Изучая сравнения и замены, сделанные во время процедуры, мы можем заметить, что количество операций пропорционально высоте соответствующего двоичного дерева, которая равна O(log n).

4. Итеративный анализ. Хотя max-heapify обычно реализуется с использованием рекурсивного подхода, его также можно реализовать итеративно. В этом случае временная сложность остается той же, т. е. O(log n), поскольку количество итераций, необходимых для удовлетворения свойства кучи, пропорционально высоте кучи.

Подводя итог, можно сказать, что процедура max-heapify при пирамидальной сортировке имеет временную сложность O(log n), независимо от используемого аналитического метода.