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

0

Одно из условий достижения успеха — умение правильно расставлять приоритеты. Спокойным субботним днем после обеда, выбирая между возможностью вздремнуть, посмотреть телевизор, сыграть в футбол или изучить следующую главу этой книги, целеустремленный студент выберет последнее. За пределами студенческого городка приоритеты приобретают еще большее значение. Рассмотрим, к примеру, ситуацию, в которой находятся сотрудники центра управления полетами аэропорта при необходимости принятия решения, какому из находящихся в воздухе самолетов предоставить посадочную полосу. Приоритетность того или иного рейса будет определяться не только расстоянием между самолетом и аэропортом, но и количеством оставшегося на борту горючего. Выбор рейса для посадки может быть жизненно важным решением. В качестве еще одного примера можно привести пассажирку, желающую вместе с несколькими страждущими попасть на уже заполненный рейс, которой служащий аэропорта пообещал предоставить освободившееся место. Вряд ли она догадывается, что приоритет и здесь будет отдан не первому в очереди, а имеющему определенный статус — более дорогие билеты, – постоянный клиент авиакомпании и тому подобное.

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

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

В разделе 7.1 представлен АТД «очередь с приоритетами». В разделе 7.2 описаны два вида реализации такой очереди для работы с последовательностями. Это простые реализации, но, к сожаление, не очень надежные.

Однако даже в таком виде они позволяют без труда объяснить два хорошо известных алгоритма — алгоритм сортировки ввода (insertion-sort) и алгоритм сортировки выбора (select-sort). В разделе 7.3 приводится более надежный вариант реализации очереди с приоритетами, в основу которой заложена конкретная структура данных, известная как пирамида (heap). Пирамида использует богатые иерархические возможности бинарных деревьев для поддержки операций формирования очередей с приоритетами в логарифмическом времени, в результате чего имеется быстрый алгоритм хранения, известный как пирамидальная сортировка (heap-sort). JB заключение приводится модель проектирования, известная как локатор (locator).

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

По теме:

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