Главная » Java, Структуры данных и алгоритмы » Пирамида

0

Одной из наиболее эффективных реализаций очереди с приоритетами служит структура данных под названием пирамида (heap). Эта структура позволяет как вводить, так и удалять элементы в логарифмическом времени, что значительно быстрее по сравнению с реализациями с помощью последовательности, рассмотренными в разделе 7.2. Фундаментальным принципом, за счет которого достигается повышение эффективности, является отказ от идеи сортировки элементов и ключей в последовательности, вместо чего используется сортировка элементов и ключей в бинарном дереве.

льная структура данных

(см. рис. 7.3) представляет собой бинарное дерево Т, содержащее в своих составных узлах набор ключей и удовлетворяющее двум дополнительным свойствам — свойству отношений (relational property), определяющему способы хранения ключей в дереве Г, и структурному свойству (structural property), определяющему свойства узлов самого дерева. Будем исходить из того, что отношения полного упорядочения могут быть представлены, например, компаратором. Отметим, что в таком определении пирамиды простой узел дерева Г не содержит ни ключей, ни элементов, а служит только в качестве «заглушки».

Свойство отношений в дереве Т, определяемое в приведенной терминологии порядка хранения ключей, можно сформулировать следующим образом.

Рис. 7.3. Пример хранения в пирамиде 13 целочисленных ключей. Последним является узел, в котором хранится ключ 8. Все простые узлы пусты

Свойство упорядоченности пирамиды (heap-order property). В пирамиде-дереве Т каждый ключ, хранящийся в узле v, отличном от корня, будет больше или равен ключу, хранящемуся в родительском элементе v.

Как следствие, ключи на пути от корня к составному узлу пирамиды Т располагаются в возрастающем порядке. К тому же наименьший ключ всегда хранится в корне дерева. Это основной ключ, неофициально считающийся «вершиной пирамиды», что и послужило основанием для названия описываемой структуры. Кстати, пирамида как структура данных не имеет ничего общего с динамической памятью (memory heap), используемой в программных средах, поддерживающих языки типа Java (см. п. 4.2.3).

Если компаратор создан так, что является обратным по отношению к полному упорядочению юпочей (то есть вызов isLessThan (3,2) по-прежнему будет возвращать true), то в корне пирамиды будет наибольший ключ. Подобное изменение «ничего не стоит», учитывая применение компараторной модели. В терминах компаратора получим, что наименьшим ключом при «обратном» определении компаратора будет наибольший. Таким образом, не ограничивая универсальности, приходим к выводу, что всегда желательно наличие наименьшего ключа в корне пирамиды.

Для повышения эффективности алгоритма, как это станет ясно немного позже, необходимо, чтобы пирамида Т имела наименьшую возможную высоту. Для установления возможного предела высоты необходимо, чтобы пирамида Т обладала дополнительным свойством полноты (complete). Если считать, что уровень / бинарного дерева Т представляет собой набор узлов с глубиной /, то указанное свойство можно сформулировать следующим образом.

Полное бинарное дерево (complete binary tree). Бинарное дерево Тс высотой h является полным, если уровни 1, 2, 3, …, h – 1 имеют максимально возможное число узлов (то есть уровень / имеет 2′ узлов, при этом О < / < h -1), а на уровне h- 1 все составные узлы расположены слева от простых узлов.

Требование расположения составных узлов уровня h – 1 слева от простых предполагает, что при стандартном проходе по дереву (например, симметричном) все составные узлы проходятся перед простыми узлами данного уровня. То есть при стандартном отображении бинарного дерева все составные узлы уровня h – 1 располагаются слева от простого узла этого уровня. При этом, поскольку пирамида Г должна быть полной, появляется еще один очень важный узел пирамиды Т, отличный от корня, а именно — последний узел дерева, который должен быть самым правым, самым глубоким составным узлом пирамиды. Немаловажным следствием условия полноты Г является утверждение 7.5.

Утверждение 7.1. Т, сортирующая п ключей, имеет высоту

Доказательство. Поскольку Гявляется полной пирамидой, количество составных узлов Т составляет как минимум

Нижний предел достигается в случае расположения на уровне h – 1 только одного составного узла.

Точно так же, поскольку Т — завершенная пирамида, определяется и максимальное количество составных узлов

Верхний предел достигается в случае, когда все узлы 2Л-1 уровня h – 1 являются составными. И поскольку количество составных узлов равно количеству ключей п

то и

Таким образом, применяя операцию логарифмирования к обоим неравенствам, видно, что

и

из чего следует

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии