Структуры данных и модели вычислений
Представление приоритетной очереди с помощью d-кучи
Представление приоритетной очереди с помощью -кучи основано на использовании так называемых завершенных -арных деревьев ().
Завершенное -арное дерево — это корневое дерево со следующими свойствами:
- Каждый внутренний узел (то есть узел, не являющийся листом дерева), за исключением, быть может, только одного, имеет ровно
потомков. Один узел-исключение может иметь от до
потомков.
- Если — глубина дерева, то для любого
такое дерево имеет ровно узлов глубины .
- Количество узлов глубины в дереве глубины
может варьироваться от до . Это свойство является следствием первых двух.
Узлы завершенного -арного дерева принято нумеровать следующим образом: корень получает номер 0, потомки узла с номером
получают номера: , , , . Такая нумерация удобна тем, что позволяет разместить узлы дерева в массиве в порядке возрастания их номеров, при этом позиции потомков любого узла в массиве легко вычисляются по позиции самого узла. Так же легко по позиции узла вычислить позицию его родителя. Так, для узла, расположенного в позиции , родительский узел располагается в позиции , где — операция деления нацело.
В изображении завершенного -арного дерева узлы одинаковой глубины удобно располагать на одном уровне, при этом потомки одного узла располагаются слева направо в порядке объявленных номеров. При таком рисовании нижний уровень заполняется, возможно, не полностью.
Отметим некоторые простые утверждения о завершенных -арных деревьях, которые будут полезны при анализе трудоемкости основных операций.
Утверждение 1.
Длина пути из корня завершенного -арного дерева с узлами в любой лист удовлетворяет неравенствам:
Доказательство
Минимальное количество узлов в -куче высоты
(), по свойствам 2 и 3 -арного дерева, очевидно, равно
(последний уровень содержит лишь один узел).
Максимальное количество узлов в такой -куче равно (последний уровень содержит узлов). Отсюда имеем неравенства:
Суммируя левую и правую части как геометрические прогрессии, получим
и после некоторых очевидных оценок с помощью логарифмирования получаем требуемые неравенства:
