Очереди с приоритетом подсказывают простой алгоритм сортировки вектора: сначала элементы один за другим помещаются в очередь, а затем извлекаются оттуда. Такой алгоритм легко закодировать на C++, используя класс priqueue (листинг 14.7).
Листинг 14.7. Сортировка с помощью очереди с приоритетом
tempiate<class Т>
void pqsort(T v[]. int n)
{ pn queue<T> oq( n ) . int i .
for (i = 0. l < n. i++) pq.insert С v[l ]) . for (i = 0. l < n. i++)
v[i] = pq extractmin() :}
Операции вставки и извлечения элементов общим количеством 2п в худшем случае выполняются за время 0{п log п), что превосходит характеристику алгоритма быстрой сортировки из главы 11 для худшего случая — 0(п2). К сожалению, дополнительный массив х[0..п], в котором размещается куча, занимает п+1 слов памяти.
Перейдем к сортировке с помощью кучи (heapsort), которая по некоторым параметрам превосходит только что описанный алгоритм. Эта сортировка описывается более коротким алгоритмом, требует меньше памяти (поскольку не задействует дополнительный массив) и выполняется быстрее. При описании этого алгоритма мы будем предполагать, что функции siftup и siftdown были изменены так, чтобы на вершине кучи оказывался наибольший элемент. Этого проще всего достичь, поменяв знаки < и > на противоположные.
Наш первый алгоритм работал с двумя массивами, один из которых содержал сортируемые элементы, а второй использовался для представления очереди. Сортировка с помощью кучи экономит память, работая с одним массивом. Один-един- ственный массив х в этой реализации представляет две абстрактные структуры: кучу с левого конца и изначально неупорядоченную последовательность элементов с правого, причем к концу работы эта последовательность оказывается отсортирована. На рис. 14.8 показано, как меняется состояние массива с течением времени. Массив отложен по горизонтальной оси, а время — по вертикальной.
Опубликовал vovan666
April 17 2013 00:04:22 ·
0 Комментариев ·
3366 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
