D-куча¶

D-куча (d-ary heap, d-ичная куча) — это структура данных, представляющая собой приоритетную очередь, реализованную в виде полного d-ичного дерева. В отличие от бинарной кучи (2-кучи), каждый узел в d-куче имеет не более d дочерних элементов. D-куча обобщает понятие бинарной кучи и позволяет настраивать производительность операций за счёт выбора параметра d. Основные свойства: для любого узла (кроме корня) его значение не меньше (в min-куче) или не больше (в max-куче) значения родительского узла; дерево является полным — все уровни, кроме последнего, заполнены полностью, а последний уровень заполняется слева направо.

¶История

Концепция d-кучи была впервые предложена Дональдом Кнутом в 1973 году в третьем томе его фундаментального труда «Искусство программирования» (The Art of Computer Programming). Кнут исследовал возможность обобщения бинарной кучи на случай произвольного числа потомков, чтобы оптимизировать время выполнения операций вставки и извлечения минимума в зависимости от конкретных задач. Впоследствии d-кучи получили развитие в работах по анализу алгоритмов и структурам данных, в частности, в контексте улучшения алгоритмов Дейкстры и Прима для работы с графами.

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

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

Основные характеристики:

• Количество узлов: n.
• Высота дерева: h = ⌈log_d (n(d-1) + 1)⌉ − 1, что приблизительно равно log_d n. Высота уменьшается с ростом d.
• Количество дочерних узлов: от 0 до d.
• Индексация: при хранении в массиве (нумерация с 0 или 1) для узла с индексом i дочерние узлы имеют индексы от d·i + 1 до d·i + d (при нумерации с 0) или от d·i − (d−2) до d·i + 1 (при нумерации с 1). Родительский узел для i-го элемента находится по формуле floor((i−1)/d) (при нумерации с 0).

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

Все операции с d-кучей, как правило, выполняются за время O(log_d n) или O(d·log_d n), в зависимости от операции.

¶Вставка (insert)

Новый элемент добавляется в конец массива (последний лист на последнем уровне). Затем выполняется процедура «просеивания вверх» (sift-up или bubble-up): элемент сравнивается с родителем, и если нарушается свойство кучи, они меняются местами. Процесс повторяется до восстановления свойства. Время выполнения: O(log_d n).

¶Извлечение минимума (extract-min)

Извлекается корневой элемент (минимальный в min-куче). На его место ставится последний элемент массива. Затем выполняется процедура «просеивания вниз» (sift-down или heapify): элемент сравнивается с d дочерними узлами, выбирается наименьший (для min-кучи), и если он меньше текущего, происходит обмен. Процесс повторяется. Время выполнения: O(d·log_d n), так как на каждом уровне требуется сравнить d дочерних узлов.

¶Поиск минимума (find-min)

Возвращается корневой элемент. Время выполнения: O(1).

¶Уменьшение ключа (decrease-key)

Используется в алгоритмах на графах (например, Дейкстры). Значение ключа узла уменьшается, после чего выполняется просеивание вверх. Время выполнения: O(log_d n).

¶Удаление произвольного узла (delete)

Сначала значение ключа узла уменьшается до минимально возможного (например, до минус бесконечности), затем выполняется извлечение минимума. Время выполнения: O(d·log_d n).

¶Выбор параметра d

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

• Малое d (например, 2 или 3): даёт меньшую высоту дерева, но большее количество сравнений на каждом уровне при просеивании вниз. Оптимально для задач, где преобладает извлечение минимума.
• Большое d (например, 4–8): уменьшает высоту дерева, что ускоряет вставку, но увеличивает время просеивания вниз из-за большего числа сравнений. Подходит для алгоритмов с частыми вставками, например, для алгоритма Дейкстры на разреженных графах.
• Эмпирические рекомендации: для большинства практических задач оптимальным считается d = 4 или d = 8. В некоторых реализациях (например, в библиотеке Boost C++) используется d = 4 по умолчанию.

Теоретически, время выполнения операций вставки и извлечения можно выразить как:

• Вставка: O(log_d n)
• Извлечение: O(d·log_d n)

Суммарное время для m операций вставки и k операций извлечения: O(m·log_d n + k·d·log_d n). Выбор d, минимизирующий это выражение, зависит от отношения m/k.

¶Применение

D-кучи находят применение в различных алгоритмах и системах:

• Алгоритм Дейкстры: для поиска кратчайших путей в графах. D-куча позволяет ускорить операции уменьшения ключа и извлечения минимума. Для разреженных графов (с малым средним числом рёбер на вершину) часто используется d = 2 или d = 3, для плотных — d = 4–8.
• Алгоритм Прима: для построения минимального остовного дерева. Аналогично алгоритму Дейкстры, d-куча улучшает производительность.
• Сортировка кучей (heapsort): хотя обычно используется бинарная куча, d-куча может быть применена для сортировки, но с учётом увеличенного времени просеивания вниз.
• Приоритетные очереди общего назначения: в системах реального времени, планировщиках задач, симуляторах.
• Сжатие данных: в алгоритме Хаффмана для построения оптимальных префиксных кодов.

¶Сравнение с другими структурами

D-куча проще в реализации, чем фибоначчиева или биномиальная куча, и требует меньше памяти на служебные структуры. Однако она уступает фибоначчиевой куче по асимптотике для операций уменьшения ключа.

¶Реализация

D-куча обычно реализуется на основе массива, что обеспечивает компактное хранение и быстрый доступ. Примерная структура на псевдокоде для min-кучи:

``` class DHeap: array: list d: int

function parent(i): return floor((i-1)/d)

function child(i, k): return d*i + k + 1 // k от 0 до d-1

function siftUp(i): while i > 0 and array[parent(i)] > array[i]: swap(array[i], array[parent(i)]) i = parent(i)

function siftDown(i): while true: minChild = i for k in 0..d-1: c = child(i, k) if c < size and array[c] < array[minChild]: minChild = c if minChild != i: swap(array[i], array[minChild]) i = minChild else: break

function insert(key): array.append(key) siftUp(size-1)

function extractMin(): min = array[0] array[0] = array[size-1] array.pop() siftDown(0) return min ```

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

Основной недостаток d-кучи — увеличенное время просеивания вниз при большом d, что может нивелировать выигрыш от уменьшения высоты. Кроме того, при d > 2 возрастает количество операций сравнения на каждом уровне, что может быть критично для больших наборов данных. В некоторых случаях (например, при очень частых извлечениях минимума) бинарная куча оказывается эффективнее.

D-куча также не поддерживает эффективное слияние (merge) двух куч, в отличие от фибоначчиевой или биномиальной куч. Для задач, требующих частого слияния, d-куча не подходит.

¶Источники

• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск. — М.: Вильямс, 2007.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
• Sedgewick R., Wayne K. Algorithms. — 4th ed. — Addison-Wesley, 2011.
• Weiss M. A. Data Structures and Algorithm Analysis in C++. — 4th ed. — Pearson, 2014.