Слабая куча
-
Описание слабой кучи
- Слабая куча — это структура данных для приоритетных очередей, сочетающая функции двоичной и биномиальной кучи.
- Хранится в массиве в виде неявного двоичного дерева.
- Обладает гарантиями эффективности биномиальных куч.
-
Инварианты и структура
- У корневого узла нет левого дочернего узла.
- Для каждого узла значение больше или равно значениям в правом поддереве.
- Листья имеют высоту, равную расстоянию между ними.
- Структура похожа на биномиальную кучу, но использует одно несовершенное дерево.
-
Операции со слабыми кучами
- Каждый узел можно считать корнем меньшей слабой кучи.
- Узел высотой h имеет h − 1 дочерних элементов.
- Выделенный предок находится на log2n уровнях выше.
- Объединение двух куч требует одного сравнения.
-
Сортировка по слабой куче
- Слабые кучи могут использоваться для сортировки массива.
- Сначала создается слабая куча, затем корень заменяется последним элементом.
- Просеивание вниз выполняется при сравнении h = ⌈log2n⌉.
-
Операции с приоритетной очередью
- В слабой максимальной куче максимальное значение находится в корне.
- Поддерживаются типичные операции приоритетной очереди: вставка, удаление, уменьшение ключа.
- Просеивание производится аналогично бинарной куче.
-
История и области применения
- Слабые кучи введены Даттоном в 1993 году.
- Использовались для сортировки n элементов с n сравнений log2n + O(n).
- Позже исследовались как структура данных приоритетной очереди.
-
История слабых куч
- Слабые кучи были введены Даттоном в 1993 году.
- Они являются частью альтернативного алгоритма сортировки кучи.
- В отличие от стандартной сортировки кучи, слабые кучи используют только n сравнений log2n + O(n) для сортировки n элементов.
-
Применение слабых куч
- Слабые кучи могут использоваться для сортировки n элементов.
- Они более широко применимы, чем стандартная сортировка кучи.
-
Исследование слабых куч
- Слабые кучи были исследованы как структура данных приоритетной очереди.
- Они могут быть использованы для различных задач, таких как управление приоритетами и обработка очередей.