Процедура heapify¶

Heapify — это процедура восстановления свойства двоичной кучи (binary heap) в массиве или части массива, представленном в виде полного двоичного дерева. Heapify применяется, когда структура кучи нарушена в одном узле (обычно корневом или в узле, чьи дочерние элементы удовлетворяют свойству кучи, а сам узел — нет). Процедура «просеивает» элемент вниз по дереву, меняя его местами с наибольшим (для max-heap) или наименьшим (для min-heap) дочерним элементом, пока не будет восстановлено свойство кучи. Heapify является ключевой операцией в алгоритмах сортировки кучей (heapsort) и построения кучи (build heap), а также в реализации очередей с приоритетом.

¶История и происхождение

Понятие кучи (heap) как структуры данных было введено Дж. Уильямсом в 1964 году в контексте алгоритма heapsort. Уильямс описал процедуру «просеивания» (sift-down), которая впоследствии стала известна как heapify. В 1973 году Р. Флойд предложил более эффективный алгоритм построения кучи (build heap), основанный на многократном вызове heapify для всех внутренних узлов, начиная с последнего. Этот метод, получивший название «метод Флойда», до сих пор является стандартным. В последующие десятилетия heapify изучалась в контексте анализа сложности, параллельных вычислений и оптимизации памяти.

¶Определение и свойства кучи

Двоичная куча — это полное двоичное дерево, в котором для каждого узла выполняется свойство кучи:

• Max-heap: значение родительского узла больше или равно значениям его дочерних узлов.
• Min-heap: значение родительского узла меньше или равно значениям его дочерних узлов.

Массив, представляющий кучу, индексируется с 0 (или 1). Для узла с индексом i:

• Левый дочерний элемент: 2*i + 1 (при индексации с 0).
• Правый дочерний элемент: 2*i + 2.
• Родительский элемент: (i-1)//2.

Heapify вызывается, когда в узле i нарушено свойство кучи, но его дочерние поддеревья (если они существуют) уже являются кучами.

¶Алгоритм heapify

¶Описание шагов (для max-heap)

1. Пусть largest = i (индекс текущего узла).
2. Вычислить индексы левого (left = 2i + 1) и правого (right = 2i + 2) дочерних элементов.
3. Если left < n (где n — размер массива) и arr[left] > arr[largest], то largest = left.
4. Если right < n и arr[right] > arr[largest], то largest = right.
5. Если largest != i:

• Поменять местами arr[i] и arr[largest].
• Рекурсивно (или итеративно) вызвать heapify для largest.

1. Если largest == i, процедура завершается — свойство кучи восстановлено.

¶Итеративная реализация

Итеративный вариант heapify использует цикл вместо рекурсии, что позволяет избежать переполнения стека при больших размерах кучи. Алгоритм повторяет шаги 1–5 до тех пор, пока largest не станет равным i или пока не будет достигнут лист дерева.

¶Для min-heap

Алгоритм аналогичен, но вместо поиска наибольшего элемента ищется наименьший. Условия сравнения меняются: arr[left] < arr[smallest] и arr[right] < arr[smallest].

¶Сложность

Временная сложность heapify для одного узла составляет O(log n) в худшем случае, где n — размер кучи. Это связано с тем, что элемент может быть «просеян» вниз до самого нижнего уровня дерева, высота которого равна log2(n). В среднем случае сложность также оценивается как O(log n).

Важно: при построении кучи (build heap) с помощью многократного вызова heapify для всех внутренних узлов общая сложность составляет O(n), а не O(n log n), как можно было бы предположить. Это объясняется тем, что количество узлов на каждом уровне убывает, а время работы heapify для узла на уровне k пропорционально (h - k), где h — высота дерева. Суммирование по всем уровням даёт линейную оценку.

¶Применение

¶Построение кучи (build heap)

Процедура build heap создаёт кучу из неупорядоченного массива. Для этого heapify вызывается для всех внутренних узлов, начиная с последнего (индекс (n//2) - 1 при индексации с 0) и до корня. Этот метод гарантирует, что после обработки каждого узла его поддеревья уже являются кучами.

¶Сортировка кучей (heapsort)

Алгоритм heapsort состоит из двух этапов:

1. Построение max-heap из исходного массива (build heap).
2. Многократное извлечение корневого элемента (максимума) и помещение его в конец массива, с последующим вызовом heapify для уменьшенной кучи.

Heapify в heapsort вызывается после каждой замены корня с последним элементом, что позволяет восстановить свойство кучи для оставшейся части массива.

¶Очереди с приоритетом

В реализации очереди с приоритетом на основе кучи heapify используется при удалении элемента с наивысшим приоритетом (извлечение корня). После замены корня последним элементом вызывается heapify для корня, чтобы восстановить структуру.

¶Другие алгоритмы

Heapify применяется в алгоритмах, требующих динамического поддержания порядка, например, в алгоритме Дейкстры для поиска кратчайших путей (при использовании кучи в качестве очереди с приоритетом), в алгоритме Прима для минимального остовного дерева, а также в некоторых задачах обработки потоков данных (top-k elements).

¶Пример на псевдокоде

``` function heapify(arr, n, i): largest = i left = 2i + 1 right = 2i + 2

if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right

if largest != i: swap(arr[i], arr[largest]) heapify(arr, n, largest) ```

¶Варианты и модификации

¶Heapify для d-ичных куч

В d-ичной куче каждый узел имеет до d дочерних элементов. Процедура heapify в этом случае сравнивает родительский элемент со всеми дочерними и выбирает наибольший (или наименьший). Временная сложность составляет O(d * log_d(n)), так как на каждом уровне требуется до d сравнений.

¶Параллельный heapify

В многопоточных или векторных реализациях heapify может быть распараллелен путём обработки нескольких узлов одновременно, особенно на верхних уровнях дерева, где поддеревья независимы. Однако из-за зависимости данных (после изменения узла требуется проверить его дочерние) полная параллелизация сложна.

¶In-place heapify

Heapify всегда работает in-place (на месте), то есть не требует дополнительной памяти, кроме стека вызовов (при рекурсивной реализации) или небольшого количества переменных (при итеративной). Это делает её эффективной для встроенных систем и ограниченных сред.

¶Ограничения и критика

• Рекурсивная реализация может привести к переполнению стека при очень больших размерах кучи (например, более 10^6 элементов), поэтому в промышленных реализациях предпочитают итеративный вариант.
• Неустойчивость: heapify не сохраняет относительный порядок равных элементов, что может быть недостатком в некоторых приложениях.
• Зависимость от размера: хотя сложность O(log n), на практике heapify может быть медленнее других операций с кучей (например, вставки) из-за необходимости многократных сравнений и обменов.

¶Источники

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347–348.
• Floyd, R. W. (1964). Algorithm 245: Treesort. Communications of the ACM, 7(12), 701.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.