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

0

/

Приложения обычно требуют выполнения сравнений и расположения объектов согласно параметрам или свойствам, предписанным каждому из них и получившим название «ключей». Формально определим ключ как объект, предписываемый элементу в качестве его специфического атрибута, который можёт бытЬ!испоЛьзован для идентификации, ранжирования или взвешивания элемента! Заметив, что ключ обычно присваивается элементу либо пользователем, либо приложением; следовательно, ключ может представлять свойбтво, которым сам элемент в действительности может и не управлять![17]

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

В приведенном выше примере с аэропортом используемый для сравнения ключ обычно представляет собой нечто большее, чем цифровое значение цены, длины, веса или скорости. Это означает, что ключ может

обладать более сложным свойством, которое не передается числом. Например, приоритетность ожидающих в очереди пассажиров обычно определяется целым набором факторов — статус постоянного клиента, стоимость билета, время регистрации. В некоторых приложениях ключ объекта является частью самого объекта (например, он может быть экземпляром переменной, хранящей цену книги или вес автомобиля). В других приложениях ключ не является частью объекта, но объект получает свой ключ от приложения (например, коэффициент качества акций, определенный финансовым экспертом, или очередность пассажиров, установленная ответственным служащим аэропорта).

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

Сравнение ключей и полное упорядочение

Очередь с приоритетами предполагает наличие непротиворечивого правила сравнения. Чтобы это правило, которое обычно представляется с помощью знака «<», было стабильным, оно должно определять отношения полного упорядочения (total order), что означает применимость правила к каждой паре ключей и соответствие следующим требованиям:

•    рефлективность: к < к;

•    асимметричность: если к\ < к2 и к2 < к\, то к\ = к2\

•    транзитивность: если к\ < к2и к2< к3, то к\ < к3.

Любое правило сравнения, удовлетворяющее указанным свойствам, не приводит к противоречию. На деле это правило определяет линейную упорядоченность некоторого множества ключей. Следовательно, если (ограниченный) набор элементов полностью упорядочен согласно некоторому принципу, то понятие наименьшего ключа кт\п вполне можно представить в виде ключа, для которого будет справедливо утверждение кт\п < к, где к — любой другой ключ этого набора.

Очередь е приоритетами (priority queue) — это контейнер с элементами, каждый из которых имеет соответствующий ключ, присвоенный при вводе элемента. Название «очередь с приоритетами» вытекает из задания с помощью ключей «приоритетности» элемента, предназначенного для удаления.

Два основных метода очереди с приоритетами Р/

Кстати, многие применяют метод removeMin как метод «extractMin», чтобы подчеркнуть возможность одновременного удаления и возвращения наименьшего элемента из очереди Р. Существует немало приложений, в которых операции removeMin играют существенную роль. Одно из таких приложений приводится ниже.

Пример 7.1. Предположим, авиарейс полностью укомплектован за час до вылета. Учитывая возможность возврата билетов, авиакомпания формирует очередь дополнительных претендентов на невостребованные на этот рейс билеты. Приоритетный статус каждого претендента в этой очереди определяется стоимостью билета (классом), который он желает приобрести, количеством совершенных им до этого полетов самолетами компании, временем обращения за билетом. Сведения о претендентах задаются при обращении за билетом с помощью операции insertltem в очередь с приоритетами. Незадолго до вылета лайнера при наличии освободившихся мест (например, из-за опоздания или отказа от полета кого-либо из пассажиров) претенденту с наивысшим приоритетом продается билет, и он удаляется из приоритетной очереди с помощью операции removeMin. И этот процесс будет повторяться до тех пор, пока не будут заполнены все пустующие места или не закончится очередь.

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

По теме:

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