Главная » Java, Структуры данных и алгоритмы » Реализация очереди с приоритетами с помощью пирамиды

0

В этом разделе покажем способ реализации АТД «очередь с приоритетами» с помощью пирамиды. Представленная структура данных очереди состоит из следующих элементов (см. рис. 7.4):

•          heap (пирамида) — полное бинарное дерево Г, элементы которого хранятся в составных узлах и имеют ключи, отвечающие требованиям упорядоченного дерева. В рассматриваемом случае бинарное дерево Г реализовано вектором, как описано в п. 6.4.1. Для каждого составного узла v дерева допределен ключ элемента k{v), хранящийся в v;

•          last (последний) — ссылка на последний узел дерева Т. Имея векторную реализацию Т, такая переменная экземпляра будет целочисленным индексом для ячейки вектора, хранящей последний узел дерева Т;

•           сотр — компаратор, определяющий отношения между ключами.

Обратите внимание, что в случае реализации пирамиды Т вектором индекс последнего составного узла w всегда равен п, а первый пустой простой узел z имеет индекс, равный п + 1 (см. рис. 7.5). Индекс z сохраняется даже в случаях:

•          если текущий последний узел w есть самый правый узел своего уровня, то z является самым левым узлом самого нижнего уровня (см. рис. 7.5, Ь;

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

Более простой способ представления пирамиды Ту вытекающий из векторного представления, поможет разобраться с методами реализации АТД «очередь с приоритетами». Например, методы обновления expandExternal(z) и re move Above External (z) могут выполняться за 0(1) времени (при отсут-

Рис. 7.4. Неар-реализация очереди с приоритетами при целочисленных ключах и буквенных элементах. Каждый узел пирамиды хранит пару «элемент-ключ». Упорядоченное дерево (пирамида) учитывает только ключи и игнорирует элементы

ствии необходимости расширять вектор), так как они Должны найти только одну ячейку в векторе. Если пользоваться такой структурой, то и методам size и isEmpty потребуется 0(1) времени. К тому же методы minElement и minKey тоже могут выполняться за 0(1) времени, обращаясь к элементу или ключу, хранящемуся в корне пирамиды (который является первой позицией в векторе). Более того, поскольку Т является полным бинарным деревом, вектор, соответствующий пирамиде Т при векторной реализации бинарного дерева, будет иметь 2п + 1 элементов, п + 1 из которых являются заглушками — простыми узлами. То есть, так как индексы простых узлов больше индексов составных узлов, можно не сохранять все простые узлы явным образом (см. рис. 7.5).

Теперь рассмотрим, как выполнить метод insertltem из АТД «очередь с приоритетами» с помощью пирамиды Т. Для сохранения новой пары «элемент-ключ» (к,ё) в Г добавляется новый составной узел. Чтобы Тоставалась полным бинарным деревом, новый составной узел добавляется так, чтобы он стал последним узлом Т. Это означает необходимость определения правильного простого узла z, над которым возможно выполнение операции expandExternal^) нового элемента, а также вставка этого

нового элемента в z, сохраняя ГЬолным (см. рис. 7.6, а-b. Узел z в таком случае называется позицией ввода (insertion position).

Обычно узел z является простым узлом, расположенным справа от последнего узла w (см. рис. 7.5, а). В любом случае, в соответствии с векторной реализацией Г, позиция ввода z хранится на месте п + 1, где п — текущий размер пирамиды. Следовательно, в векторной реализации узел z идентифицируется за постоянное время. После выполнения expandExternal(z) узел z становится последним составным узлом, в который и сохраняется новая пара «элемент-ключ» (к,е), такая, что k(z) = к.

Процесс восходящей Сортировки после ввода

После проделанной операции дерево Гостается полным, но при этом может нарушиться его упорядоченность. Следовательно,, до тех пор пока узел z не является корнем Т (то есть очередь с приоритетами до ввода была пустой), ключ k{z) сравнивается с ключом к(и), хранящимся в родительском элементе и узла z. Если к{и) > k(z), то построение должно быть упорядочено, что может достигаться локальной заменой пар (к,е), хранящихся в z и и (см. рис. 7.6, c-d). Подобный обмен заставляет новую пару подняться на уровень вверх. И в этом случае опять может оказаться так, что порядок в пирамиде нарушен, и тогда замена одной пары на другую повторяется. Этот процесс продолжается до тех пор, пока все пары (к,е) не выстроятся в порядке, определенном свойствам упорядоченности дерева (см. рис. 7.6, e-h).

Рис. 7.5. Последний узел w и первый простой узел z в пирамиде: (а) традиционный случай — z распложен справа от w; (b) z — самый левый узел нижнего уровня. Векторное представление (а) показано на рисунке (с); представление (Ь) показано на рисунке (d)

 

 

 

Рис. 7.5. Ввод нового элемента с ключом 2 в пирамиду рис. 7.4: (а) первоначальный вид; (Ь) добавление нового последнего узла справа от предыдущего последнего узла; (c-d) локальный обмен пар для восстановления свойства упорядочения; (e-f) очередной обмен; (g-h) последний обмен

Продвижение вверх по пирамиде в результате поочередных обменов получило название восходящей сортировки (up-heap bubbling). Обмен либо решает проблему нарушения свойства упорядочения, либо передает ее на один уровень вверх. В крайнем случае восходящая сортировка заставляет новую пару проделать весь путь до самого корня пирамиды Т (см. рис. 7.6). Таким образом, время выполнения метода insertltem будет пропорционально высоте Г, что составит 0(log л), так как Т является полным деревом.

Если пирамида Т реализована в виде вектора, то последний узел z можно найти за 0(1) времени. Например, воспользуемся наследованием для расширения векторной реализации бинарного дерева, чтобы добавить метод возврата узла с индексом 1, то есть с номером уровня п + 1, как описывалось в п. 6.4.1. Или наоборот, можно даже определить мето^ add для добавления нового элемента в первый простой узел z в позицию п+ 1 вектора. Во фрагменте кода 7.7, приведенном ниже, показано использование этого метода для эффективной реализации метода insertltem. Если же пирамида Т реализована связной структурой, то потребуется применить и поиск позиции ввода z (см. упражнение 3-7.8).

Теперь обратимся к методу removeMin из АТД «очередь с приоритетами». Алгоритм выполнения метода removeMin с помощью пирамиды Т показан на рис. 7.7.

Известно, что элемент с наименьшим ключом хранится в корне г пирамиды Г (даже если таких ключей несколько). Тем не менее до тех пор пока г будет единственным составным узлом Г, просто так удалить его невозможно, поскольку это нарушит структуру бинарного дерева. Вместо этого обратимся к последнему узлу w в Г, скопируем его пару «ключ-элемент» в корень г и затем удалим последний узел w с помощью операции removeAboveExternal(r.rightChild(w)) из А1Д «бинарное дерево». Эта операция удаляет w и его правый дочерний элемент и замещает w его левым дочерним элементом (см. рис. 7.7, а-b). После завершения этой операции с постоянным временем выполнения достаточно обновить ссылку на последний узел, просто сославшись на узел в позиции п (после удаления) в векторной реализации дерева Т.

Процесс нисходящей сортировки после удаления

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

Рис. 7.7. Удаление элемента с наименьшим ключом из пирамиды: (а-b) удаление последнего узла, пара «ключ-элемент» которого сохраняется в корне; (c-d) локальное восстановление свойства упорядочения; (e-f) очередной обмен парами; (g-h) последний обмен

Если окажется, что ключ к(г), хранящийся в узле г, больше ключа k(s), хранящегося в узле s, то следует обеспечить упорядоченность дерева, чего можно добиться путем локального обмена парами «ключ-элемент», хранящимися в г и s (см. рис. 7.7, c-d) (заметим, что при этом содержимое г не меняется с содержимым братьев s). Осуществляемый обмен восстанавливает свойство упорядоченного дерева для г и s, но при этом может нарушать его на уровне s. Следовательно, процедура обмена может повторяться далее вниз по дереву Г, до тех пор пока все пары не будут упорядочены (см. рис. 7.7) e-h). Такой вид обмена пар в нисходящем направлении получил название нисходящей сортировки (down-heap bubbling). Обмен пар либо решает задачу упорядочения на один уровень вниз, либо для всего дерева в целом. В крайнем случае пара «ключ-элемент» проходит весь путь вниз до уровня, расположенного непосредственно над последним уровнем (см. рис. 7.7). Таким образом, максимальное время выполнения метода removeMin будет пропорционально высоте пирамиды Г, то есть 0(log п).

Анализ

В табл. 7.2 приведено время выполнения методов АТД «очередь с приоритетами» при реализации очереди с помощью пирамиды, в свою очередь реализованной структурой данных бинарного дерева, поддерживающей выполнение методов АТД «бинарное дерево» (за исключением elements()) за 0(1) времени. И связная структура, и векторная структура из раздела 6.4 соответствуют этому требованию.

Операция

Время

size, isEmpty

0(1)

minElement, minKey

0(1)

insertltem

0(log ri)

removeMin

0(log a)

Таблица 7.2. Производительность очереди с приоритетами, реализованной с помощью пирамиды, в свою очередь реализованной векторной структурой бинарного дерева. Здесь п указывает число элементов в очереди в момент выполнения метода. Если пирамида реализована с помощью связной структуры, то ее размер должен быть равен 0(л), а при реализации с помощью вектора — 0(N), где N> п — размер массива, используемого для реализации вектора

Короче говоря, каждый из методов АТД «очередь с приоритетами» может быть выполнен за 0(1) или 0(log п) времени, где п — количество элементов в момент выполнения метода. Анализ времени выполнения методов выглядит следующим образом:

•          поиск позиции ввода при выполнении insertltem и обновлении позиции последнего узла при выполнении removeMin занимают постоянный промежуток времени;

•          пирамида Т имеет п составных узлов, каждый из которых хранит ссылку на ключ и ссылку на элемент, а также п + 1 простых узлов.

В заключение отметим, что пирамидальная структура данных представляет собой очень эффективный вид реализации АТД «очередь с приоритетами», независимо от ее реализации с помощью связной структуры или последовательности. Пирамидальная реализация обеспечивает одинаково быстрое выполнение как ввода, так и удаления элементов, в отличие от реализаций с помощью последовательности. Важным следствием эффективности этой реализации является значительное ускорение сортировки очереди с приоритетами по сравнению с алгоритмами сортировки методом ввода и сортировки методом выбора, используемыми в реализациях с помощью последовательности.

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

По теме:

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