Структуры данных и модели вычислений

         

Представление приоритетной очереди с помощью d-кучи


Представление приоритетной очереди с помощью -кучи основано на использовании так называемых завершенных -арных деревьев ().

Завершенное -арное дерево — это корневое дерево со следующими свойствами:

  1. Каждый внутренний узел (то есть узел, не являющийся листом дерева), за исключением, быть может, только одного, имеет ровно

    потомков. Один узел-исключение может иметь от до

    потомков.

  2. Если — глубина дерева, то для любого

    такое дерево имеет ровно узлов глубины .

  3. Количество узлов глубины в дереве глубины

    может варьироваться от до . Это свойство является следствием первых двух.

Узлы завершенного -арного дерева принято нумеровать следующим образом: корень получает номер 0, потомки узла с номером

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

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

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

Утверждение 1.

Длина пути из корня завершенного -арного дерева с узлами в любой лист удовлетворяет неравенствам:

Доказательство

Минимальное количество узлов в -куче высоты

(), по свойствам 2 и 3 -арного дерева, очевидно, равно

(последний уровень содержит лишь один узел).

Максимальное количество узлов в такой -куче равно (последний уровень содержит узлов). Отсюда имеем неравенства:

Суммируя левую и правую части как геометрические прогрессии, получим

и после некоторых очевидных оценок с помощью логарифмирования получаем требуемые неравенства:



Содержание  Назад  Вперед