Бинарная куча¶

Бинарная куча — это структура данных, представляющая собой полное бинарное дерево, в котором каждый родительский узел имеет значение, не меньшее (для max-кучи) или не большее (для min-кучи) значений его дочерних узлов. Бинарная куча является частным случаем кучи (пирамиды) и широко применяется для реализации очередей с приоритетом, алгоритмов сортировки (например, пирамидальной сортировки) и в задачах, требующих быстрого доступа к максимальному или минимальному элементу.

¶Основные свойства

Бинарная куча характеризуется двумя ключевыми свойствами:

1. Свойство кучи (heap property): Для любого узла i (кроме корня) выполняется одно из двух условий:

• Max-куча: A[parent(i)] >= A[i] — значение родительского узла не меньше значения дочернего. Корень содержит максимальный элемент.
• Min-куча: A[parent(i)] <= A[i] — значение родительского узла не больше значения дочернего. Корень содержит минимальный элемент.

1. Свойство полноты (shape property): Дерево является полным бинарным деревом. Это означает, что все уровни, кроме, возможно, последнего, полностью заполнены, а на последнем уровне все узлы располагаются слева направо без пропусков.

Благодаря свойству полноты, бинарную кучу удобно хранить в виде одномерного массива. При индексации с 1 (или 0) для узла с индексом i:

• Родитель: parent(i) = floor(i/2) (или floor((i-1)/2) при индексации с 0).
• Левый дочерний узел: left(i) = 2i (или 2i + 1).
• Правый дочерний узел: right(i) = 2i + 1 (или 2i + 2).

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

¶Основные операции

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

¶Вспомогательные процедуры

• heapify (просеивание вниз): Восстанавливает свойство кучи для узла i, если его дочерние деревья являются кучами. Процедура сравнивает значение узла i с его дочерними узлами и, при нарушении свойства, меняет его местами с наибольшим (для max-кучи) или наименьшим (для min-кучи) дочерним узлом. Затем рекурсивно или итеративно применяется к тому дочернему узлу, с которым произошёл обмен. Сложность: O(log n).
• siftUp (просеивание вверх): Используется, когда значение узла становится больше (для max-кучи) или меньше (для min-кучи) значения родителя. Узел меняется местами с родителем, и процесс повторяется до корня или до восстановления свойства кучи. Сложность: O(log n).

¶Основные операции

• insert (вставка): Добавляет новый элемент в конец массива (на последний уровень кучи), а затем применяет к нему процедуру siftUp для восстановления свойства кучи. Сложность: O(log n).
• extractMax/extractMin (извлечение максимального/минимального элемента): Извлекает корневой элемент (максимальный в max-куче или минимальный в min-куче). Корень заменяется последним элементом массива, размер кучи уменьшается на единицу. Затем к новому корню применяется процедура heapify. Сложность: O(log n).
• peek/getMax/getMin (получение корня без удаления): Возвращает значение корневого элемента. Сложность: O(1).
• buildHeap (построение кучи): Преобразует неупорядоченный массив в бинарную кучу. Эффективный способ заключается в последовательном применении heapify ко всем внутренним узлам, начиная с последнего и двигаясь к корню. Сложность: O(n).
• increaseKey/decreaseKey (изменение ключа): Изменяет значение ключа узла. После изменения применяется siftUp (если ключ был увеличен в max-куче или уменьшен в min-куче) или heapify (в обратном случае). Сложность: O(log n).
• delete (удаление произвольного элемента): Удаляет элемент по известному индексу. Для этого значение ключа узла делается максимально возможным (для max-кучи) или минимально возможным (для min-кучи), затем выполняется siftUp до корня, после чего вызывается extractMax/extractMin. Сложность: O(log n).

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

Бинарная куча лежит в основе алгоритма пирамидальной сортировки. Алгоритм состоит из двух этапов:

1. Построение max-кучи из исходного массива (buildHeap).
2. Повторное извлечение корневого элемента (extractMax) и помещение его в конец отсортированной части массива. После каждого извлечения размер кучи уменьшается, а свойство кучи восстанавливается.

Сложность пирамидальной сортировки составляет O(n log n) в худшем, среднем и лучшем случаях. Она не требует дополнительной памяти (сортировка на месте), но не является устойчивой (stable).

¶Реализация

Ниже приведён пример реализации max-кучи на языке C++ с использованием массива (индексация с 0):

```cpp

¶include <iostream>

¶include <vector>

¶include <algorithm>

class MaxHeap { private: std::vector<int> heap;

int parent(int i) { return (i - 1) / 2; } int left(int i) { return 2 i + 1; } int right(int i) { return 2 i + 2; }

void heapify(int i) { int largest = i; int l = left(i); int r = right(i);

if (l < heap.size() && heap[l] > heap[largest]) largest = l; if (r < heap.size() && heap[r] > heap[largest]) largest = r;

if (largest != i) { std::swap(heap[i], heap[largest]); heapify(largest); } }

void siftUp(int i) { while (i > 0 && heap[parent(i)] < heap[i]) { std::swap(heap[i], heap[parent(i)]); i = parent(i); } }

public: void insert(int value) { heap.push_back(value); siftUp(heap.size() - 1); }

int extractMax() { if (heap.empty()) throw std::out_of_range("Heap is empty"); int max = heap[0]; heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) heapify(0); return max; }

int getMax() { if (heap.empty()) throw std::out_of_range("Heap is empty"); return heap[0]; }

void buildHeap(const std::vector<int>& arr) { heap = arr; for (int i = heap.size() / 2 - 1; i >= 0; --i) { heapify(i); } }

bool isEmpty() { return heap.empty(); } int size() { return heap.size(); }

void print() { for (int val : heap) std::cout << val << " "; std::cout << std::endl; } }; ```

¶Применение

Бинарная куча используется в различных областях информатики и программирования:

• Очереди с приоритетом: Бинарная куча — классическая реализация очереди с приоритетом, где элемент с наивысшим приоритетом (максимальный или минимальный) всегда находится в корне.
• Алгоритмы на графах: Алгоритм Дейкстры для поиска кратчайших путей и алгоритм Прима для построения минимального остовного дерева могут быть эффективно реализованы с использованием бинарной кучи для извлечения вершины с минимальным расстоянием.
• Сортировка: Пирамидальная сортировка (Heapsort) — один из основных алгоритмов сортировки, гарантирующий сложность O(n log n).
• Поиск k-го наибольшего/наименьшего элемента: С помощью min-кучи размера k можно найти k-й наибольший элемент за O(n log k).
• Слияние отсортированных массивов: Бинарная куча позволяет эффективно слить несколько отсортированных массивов в один.
• Планирование задач: В операционных системах и системах реального времени для управления задачами с приоритетами.

¶Разновидности и расширения

Существуют модификации и обобщения бинарной кучи, улучшающие её характеристики или адаптирующие для специфических задач:

• d-куча (d-арная куча): Обобщение, в котором каждый узел имеет до d дочерних узлов. Уменьшает высоту дерева до O(log_d n), что может ускорить heapify, но замедляет siftUp.
• Биномиальная куча: Структура, состоящая из набора биномиальных деревьев. Поддерживает эффективное слияние двух куч (за O(log n)).
• Куча Фибоначчи: Более сложная структура, обеспечивающая амортизированное время O(1) для вставки, изменения ключа и слияния, и O(log n) для извлечения минимума. Используется в продвинутых реализациях алгоритмов на графах.
• Двусторонняя куча (deap): Структура, позволяющая быстро получать и максимальный, и минимальный элементы.
• Медианная куча: Структура, поддерживающая быстрое получение медианы набора данных.

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

• Отсутствие эффективного поиска: Бинарная куча не поддерживает быстрый поиск произвольного элемента (кроме корня). Для поиска элемента по значению требуется линейный проход по массиву.
• Неустойчивость: Пирамидальная сортировка и другие алгоритмы на основе кучи не являются устойчивыми, то есть не сохраняют относительный порядок равных элементов.
• Ограниченная поддержка слияния: Слияние двух бинарных куч требует перестроения одной из них за O(n), что менее эффективно, чем у биномиальных куч или куч Фибоначчи.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
• Седжвик Р. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск. — М.: ДиаСофт, 2002. — 688 с.
• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2007. — 832 с.