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

0

Другим не менее важным применением очереди с приоритетами является сортировка, когда п элементов из множества S могут сравниваться в соответствии с отношениями упорядочения, и требуется реорганизовать их в порядке возрастания (или, по крайней мере, в порядке неубывания). Алгоритм сортировки So помощью приоритетной очереди Q доста- 1 точно прост и состоит из двух шагов:

1.                       На первом шаге элементы сортировки S располагаются в изначально пустой очереди с приоритетами Р с помощью серии операций insert- Item, по одному элементу за операцию.

2.                       На втором шаге элементы извлекаются из Рв неубывающем порядке с помощью серии операций removeMin, размещаются обратно в S в нужном порядке.

Псевдокод этого алгоритма приводится во фрагменте кода 7.1, исходя из предположения, что S — последовательность (псевдокод для различных коллекций типа списка или вектора идентичен). Алгоритм будет выполняться в любой очереди с приоритетами Р независимо от ее реализации. Тем не менее время выполнения алгоритма будет определяться количеством повторений операций insertltem и removeMin, которые зависят от способа реализации Р. И на самом деле, PriorityQueueSort является, скорее, «схемой сортировки», нежели алгоритмом, поскольку не показывает, как реализована очередь с приоритетами Р. Схема PriorityQueueSort используется как основа нескольких популярных алгоритмов сортировки, включая сортировку методом выбора, сортировку методом ввода и пирамидальную сортировку, и рассматривается в этой главе.

Алгоритм PriorityQueueSort^P):

Input: последовательность S из п элементов, для которых определены отношения упорядочения, и очередь с приоритетами Р, сравнивающая ключи на основе этих отношений.

Output: последовательность S, отсортированная согласно установленным отношениям упорядочения.

while S is not empty do

e <- S.removeFirst() {удалить элемент e из S} P.insertltem(e,e) {ключ представляет собой элемент} while Р is not empty do

e <r- P.removeMin() {удалить наименьший элемент из Р} S.insertLast(e) {добавить этот элемент в конец S}

Фрагмент кода 7.1. Алгоритм PriorityQueueSort. Заметьте, что элементы последовательности выступают ключами в очереди с приоритетами

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

По теме:

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