Главная » Java, Структуры данных и алгоритмы » Локаторные методы очереди с приоритетами

0

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

И хотя вышеприведенные реализации АТД «очередь с приоритетами» выполнены на основе контейнеров (последовательность и дерево), предполагающих наличие позиций, к самой очереди с приоритетами абстракция позиций не применима. Таким образом, используем локаторы для прямого доступа .к объектам очереди. Крнтейнерный класс может выда- ‘ вать локаторы объектам при вводе и принимать локаторы в качестве параметров методов быстрого обновления.

Расширение АТД «очередь с приоритетами»

С помощью локаторов расширим АТД «очередь с приоритетами» следующими методами, которые имеют ддступ и могут модифицировать очередь с приоритетами Р:

min(): возвращает локатор объекта, имеющего в Р наименьший ключ.

Input: отсутствует; Output: локатор.

insert(/:,e): вводит новый объект с элементом е и ключом к в Р и возвращает локатор этого объекта.

Input: объекты к (ключ) и е (элемент); Output: локатор.

remove(/): удаляет из Р объект, имеющий локатор /. Input: локатор; Output: отсутствует.

replaceElement(/,e): замещает на е и возвращает элемент объекта в Р9 имеющего локатор /. Input: локатор, объект; Output: объект.

replaceКеу(/,к): замещает на А: и возвращает ключ объекта с локатором /.

Input: локатор, объект; Output: объект. В нижеприведенном примере рассмотрим эти методы подробнее.

Пример 7.5. Рассмотрим следующую серию локаторных операций и их эффект при изначально пустой очереди с приоритетами Р.

Операция

Результат

Приоритетная очередь P

insert(5, А)

h

{(5, A)}

insert(3, В)

h

{(3,2?), (5, A)}

insert(7, С)

h

{(3, В), (5, A), (7, Q}

min()

h

{(3, B), (5, A), (7, Q}

key(fe)

3

{(3, B), (5, A), (7, Q}

remove^)

A

{(3, B), (7, Q}

replaceKey(/2> 9)

3

{(7, Q, (9,1?)}

key(/2)

9

{(7, С), (9.Д)}

replaceElement(/3> D)

С

{(7, D), (9,2?)}

Есть несколько областей применения локаторных методов. Например, в очереди пассажиров авиарейса пассажир-пессимист может покинуть зал ожидания раньше времени (что приводит к необходимости выполнить операцию remove)! В то же время приоритетность другого пассажира может возрасти неожиданно — после того как он вспомнит о своей «золотой карточке постоянного клиента» (что вызовет необходимость выполнения операции replaceKey). Если требуется отслеживание изменений в базе данных ожидающих пассажиров, можно реализовывать операции удаления и замещения гораздо быстрее при доступе к объектам через их локаторы. Причиной большей эффективности локаторных методов поиска является возможность кодирования в локаторах информации о реализации очереди, способствующей ускорению поиска. Локаторный поиск гораздо быстрее поиска по ключевым значениям, так как значения ключей задаются пользователем, в то время как локаторы обеспечиваются непосредственно. Например, если реализуется очередь с приоритетами с помощью несортированной последовательности, то локатор для этой очереди может хранить позицию объекта в последовательности. В этом случае доступ через локатор выполняется за 0(1) времени, а поиск

по ключу, который должен проверить всю последовательность, выполняется в худшем случае за О(п) времени.

И наконец, локаторные методы могут использоваться для реализации нелокаторных контейнерных методов. Некоторые из методов АТД «очередь с приоритетами», описанные в п. 7.1.3, могут выражаться простым комбинированием приведенных выше локаторных методов. Например, операция minElement() эквивалентна min().element(), а операция removeMin() эквивалентна сочетанию remove и min. Кроме того, иногда следует ограничить использование операции replaceKey, чтобы она могла только увеличивать или уменьшать значение ключа. Такое ограничение может быть осуществлено с помощью, например, новых методов increase- Key или decreaseKey, которые будут использовать локатор в качестве аргумента. Дальнейшие применения очереди с приоритетами, доукомплектованной локаторными методами, приведены в главе 12.

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

По теме:

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