Построение кучи¶

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

¶История

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

¶Основные определения

¶Двоичная куча

Двоичная куча — это полное двоичное дерево, в котором все уровни, кроме последнего, полностью заполнены, а последний уровень заполняется слева направо. Каждый узел дерева соответствует элементу массива. Для массива A[1..n] (индексация с 1) корень находится в A[1]; для узла с индексом i его левый потомок — A[2i], правый — A[2i+1], родитель — A[⌊i/2⌋].

¶Свойство кучи

• Max-куча: A[parent(i)] ≥ A[i] для всех i > 1 (корень — максимальный элемент).
• Min-куча: A[parent(i)] ≤ A[i] для всех i > 1 (корень — минимальный элемент).

¶Операции

• Просеивание вниз (sift-down, heapify): восстановление свойства кучи для узла, если его поддеревья уже являются кучами. Узел обменивается с наибольшим (для max-кучи) или наименьшим (для min-кучи) потомком, пока свойство не выполнится.
• Просеивание вверх (sift-up, bubble-up): восстановление свойства кучи при добавлении нового элемента в конец массива; элемент поднимается вверх, обмениваясь с родителем, пока свойство не выполнится.

¶Алгоритмы построения кучи

¶1. Построение с помощью просеивания вниз (алгоритм Флойда)

Этот метод является наиболее эффективным и используется в большинстве реализаций. Исходный массив рассматривается как полное двоичное дерево. Построение начинается с последнего узла, у которого есть хотя бы один потомок (индекс n/2, округлённый вниз), и движется к корню. Для каждого узла вызывается процедура просеивания вниз.

Псевдокод для max-кучи: ``` BuildMaxHeap(A, n): for i = n/2 downto 1: SiftDown(A, i, n)

SiftDown(A, i, n): while 2i ≤ n: child = 2i if child+1 ≤ n and A[child+1] > A[child]: child = child+1 if A[i] ≥ A[child]: break swap(A[i], A[child]) i = child ```

Временная сложность: O(n). Доказательство основано на том, что количество узлов на высоте h не превышает n/2^{h+1}, а время просеивания для узла на высоте h — O(h). Сумма по всем высотам даёт O(n).

¶2. Построение с помощью просеивания вверх (последовательное добавление)

Этот метод строит кучу путём последовательного добавления элементов в пустую кучу. Каждый новый элемент помещается в конец массива, а затем просеивается вверх.

Псевдокод для max-кучи: ``` BuildMaxHeapByInsert(A, n): heap = [] for i = 1 to n: heap.append(A[i]) SiftUp(heap, i)

SiftUp(heap, i): while i > 1 and heap[i] > heap[⌊i/2⌋]: swap(heap[i], heap[⌊i/2⌋]) i = ⌊i/2⌋ ```

Временная сложность: O(n log n). Каждая вставка требует O(log n) времени, всего n вставок.

¶3. Построение с помощью рекурсивного просеивания

Рекурсивная версия алгоритма Флойда: для каждого узла рекурсивно вызывается просеивание вниз. Однако рекурсия может увеличить накладные расходы, и на практике предпочитают итеративную реализацию.

¶Сравнение методов

¶Применение

¶Пирамидальная сортировка (heapsort)

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

¶Приоритетные очереди

Кучи используются для реализации приоритетных очередей, где операции вставки и извлечения максимума (или минимума) выполняются за O(log n). Построение кучи из набора элементов позволяет инициализировать очередь за O(n).

¶Алгоритмы на графах

В алгоритме Дейкстры для поиска кратчайших путей и алгоритме Прима для построения минимального остовного дерева часто используются приоритетные очереди на основе кучи. Построение кучи из начальных расстояний или весов рёбер ускоряет инициализацию.

¶Обработка потоков данных

В задачах, требующих поддержания порядка в скользящем окне или нахождения k-го наибольшего элемента, кучи строятся периодически для обновления данных.

¶Пример построения кучи

Рассмотрим массив [4, 10, 3, 5, 1, 8, 7] (индексация с 1). Длина n=7. Последний узел с потомком — индекс 3 (значение 3). Алгоритм Флойда:

1. i=3: узел 3 имеет потомков 6 (8) и 7 (7). Наибольший — 8. Меняем 3 и 8. Массив: [4, 10, 8, 5, 1, 3, 7].
2. i=2: узел 2 (10) имеет потомков 4 (5) и 5 (1). Свойство выполняется.
3. i=1: узел 1 (4) имеет потомков 2 (10) и 3 (8). Наибольший — 10. Меняем 4 и 10. Массив: [10, 4, 8, 5, 1, 3, 7]. Теперь узел 2 (4) имеет потомков 4 (5) и 5 (1). Наибольший — 5. Меняем 4 и 5. Массив: [10, 5, 8, 4, 1, 3, 7].

Результат: max-куча [10, 5, 8, 4, 1, 3, 7].

¶Критика и ограничения

• Чувствительность к порядку данных: алгоритм Флойда не зависит от исходного порядка, но в худшем случае (например, отсортированный в обратном порядке массив) количество обменов может быть больше, хотя асимптотика остаётся O(n).
• Неустойчивость: куча не сохраняет относительный порядок равных элементов, что может быть недостатком в некоторых приложениях.
• Кэш-неэффективность: доступ к элементам кучи происходит по индексам, которые могут быть не последовательными в памяти, что снижает производительность на больших массивах из-за промахов кэша.
• Альтернативы: для построения приоритетных очередей в некоторых случаях используются более эффективные структуры, такие как биномиальные кучи или кучи Фибоначчи, которые позволяют выполнять некоторые операции быстрее, но имеют более сложную реализацию.

¶Интересные факты

• Алгоритм Флойда был впервые опубликован в 1964 году в статье «Algorithm 245: Treesort» в журнале Communications of the ACM.
• Несмотря на то, что построение кучи за O(n) является оптимальным, на практике для небольших массивов (n < 10) последовательное добавление может быть быстрее из-за меньших накладных расходов.
• В стандартной библиотеке C++ функция std::make_heap реализует алгоритм Флойда.
• В языке Python модуль heapq предоставляет функцию heapify(), которая строит min-кучу за O(n).

¶Источники

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. «Introduction to Algorithms» (3rd ed.). MIT Press, 2009. Глава 6: Heapsort.
• Robert W. Floyd. «Algorithm 245: Treesort». Communications of the ACM, 7(12):701, 1964.
• Donald E. Knuth. «The Art of Computer Programming, Volume 3: Sorting and Searching» (2nd ed.). Addison-Wesley, 1998. Раздел 5.2.3.
• Michael T. Goodrich, Roberto Tamassia. «Algorithm Design and Applications». Wiley, 2015. Глава 9.