Очереди с приоритетом оказываются полезными во многих приложениях. В операционной системе такая структура может использоваться для обработки множества задач. Они помещаются в очередь в произвольном порядке, а следующая задача извлекается из набора: priqueue <Task> queue.
В дискретной модели элементами являются моменты событий. В цикле имитации очередное событие извлекается пз очереди (а новые могут туда добавляться):
pr1queue<Event> eventqueue.
В обоих приложениях базовый класс очереди с приоритетом должен быть расширен дополнительной информацией. В нашем обсуждении мы опустим детали реализации, но в создаваемые вами классы C++ они должны быть включены.
Последовательные структуры, такие как массивы или связанные списки, в первую очередь приходят в голову при выборе способа реализации очередей с приоритетом. Если последовательность отсортирована, извлечь наименьший элемент несложно, но трудно добавить новый. Для неупорядоченной структуры ситуация будет обратной. В табл. 14.1 отражены данные о производительности различных структур на п-элементном наборе.
Структура Вставка Извлечение п вставок и извлечений
Упорядоченная О(н) 0(1) <Э(«2)
последовательность
Кучи O(logn) <3(log л) O(nlogn)
Неупорядоченная 0(1) 0(п) О(п')
последовательность
Хотя положение элемента может быть определено с помощью двоичного поиска за время О(п), перемещение элементов для освобождения места для нового требует 0{п) операций. Если вы забыли о различии между алгоритмами, выполняющимися за время 0{п2) и 0(n\ogn), загляните в раздел 8.5 главы 8: когда п=1 ООО ООО, первая программа выполнится за три часа, а вторая — за одну секунду.
Реализация очередей с приоритетом с помощью куч — это середина между двумя крайностями. Набор из п элементов представляется с помощью массива х[1..п], обладающего свойством кучи, причем х объявляется в языках С или C++ как x[maxsize+l] (элемент х[0] не используется). Инициализация пустым множеством осуществляется с помощью присваивания п = 0. Добавляя новый элемент, мы увеличиваем п и помещаем этот элемент в х[п]. При этом возникает ситуация, для исправления которой и была придумана функция siftup: утверждение heap(l, п-1) оказывается истинным, a heap(l, п) — в общем случае ложным. Код, осуществляющий добавление нового элемента, приведен на листинге 14.4.
Опубликовал vovan666
April 17 2013 00:04:16 ·
0 Комментариев ·
3366 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
