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

0

Описав абстрактный тип данных очереди с приоритетами на интуитивном уровне, перейдем к более детальному анализу. Как АТД, очередь с приоритетами Р поддерживает следующие методы:

size(): возвращает количество элементов в очереди Р. Input: отсутствует; Output: целое число.

isEmptyO: проверяет наличие элементов в очереди Р. Input: отсутствует; Output: boolean.

insertltem(k,e): вводит новый элемент е с ключом к в очередь Р.

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

minElement(): возвращает (но не удаляет) элемент очереди Р с наименьшим ключом; ошибка возникает при пустой очереди. Input: отсутствует; Output: объект (элемент).

minKey(): возвращает наименьший ключ очереди Р; ошибка возникает при пустой очереди. Input: отсутствует; Output: объект (ключ).

removeMin(): удаляет из очереди Р и возвращает элемент с наименьшим ключом; ошибка возникает при пустой очереди. Input: отсутствует; Output: объект (элемент).

Как уже отмечалось, главными методами АТД «очередь с приоритетами» являются операции insertltem и removeMin. Остальные операции представляют собой либо второстепенные методы запроса (ininElement и minKey), либо универсальные контейнерные методы (size и isEmpty). Из этого вполне очевидно, что АТД «очередь с приоритетами» намного проще АТД «последовательность». Эта простота достигается за счет того, что элементы в очереди с приоритетами вводятся и удаляются исключительно по их ключам, в то время как в последовательности — исходя из их позиций и рангов. Таким образом, для очереди достаточно только одного метода ввода и одного метода удаления, а для последовательности требуется большое количество разнообразных методов ввода и удаления элементов. Написание Java-интерфейса для АТД «очередь с приоритетами» оставлено для упражнения М-7.1. Операции абстрактного типа данных «очередь с приоритетами» иллюстрируются следующим примером.

Пример 7.2. В нижеприведенной таблице показана серия операций и их результаты для изначально пустой очереди, в которой элемент е и его ключ к обозначены парой (к,е). Столбец «Очередь с приоритетами» содержит элементы, сортируемые по ключам. Для очереди в принципе достаточно иметь минимальное количествр пар для выполнения сортировки, определенной реализацией.

Но пока еще не рассмотрены два не менее важных вопроса:

•            Как установить связь между клЬчом и элементом? *

•            Как сравнивать ключи для определения наименьшего?

Ответы на эти вопросы требуют привлечения двух интересных моделей проектирования.

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

По теме:

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