Алгоритмы - построение и анализ (1021735), страница 36
Текст из файла (страница 36)
Получается, что время, которое требуется для преобразования неупорядоченного массива в невозрастающую пирамиду, линейно зависит от размера входных данных. Неубывающую пирамиду можно создать с помощью процедуры Вцп.п Мпч Нплг, полученной в результате преобразования процедуры Вгльп Млх Нклг путем замены в строке 3 вызова функции Млх Нелг1гу вызовом функции Млч Нвлигу (см. упражнение 6.2-2). Процедура Вин.п Мпч Нилг создает неубывающую пирамиду из неупорядоченного линейного массива за время, линейно зависящее от размера входных данных. УПРажНЕНИЯ 6.3-1. Используя в качестве модели рис.
6.3, проиллюстрируйте работу процедуры Вин.п Млх Нилв с входным массивом А = (5, 3, 17, 10,84, 19, б, 22, 9). 6.3-2. Почему индекс цикла 4 в строке 2 процедуры Виил Млх Нелр убывает от [1епдй [А]/2] до 1, а не возрастает от 1 до [ (епудь [А]/2]? 6.3-3. Покажите, что в любой и-элементной пирамиде на высоте й находится не более [п/2"+"1 узлов. 6.4 Алгоритм пирамидальной сортировки Работа алгоритма пирамидальной сортировки начинается с вызова процедуры Вглп> Млх Ннлг, с помощью которой из входного массива А [1. п], где Часть й. Сортировка и порядковая статистика 188 и = 1еидй [А], создается невозрастающая пирамида. Поскольку наибольший элемент массива находится в корне, т.е. в элементе А [1], его можно поместить в окончательную позицию в отсортированном массиве, поменяв его местами с элементом А И. Выбросив из пирамиды узел и (путем уменьшения на единицу величины Ьсар згге [А]), мы обнаружим, что подмассив А [1..
(и — 1)] легко преобразуется в невозрастающую пирамиду. Пирамиды, дочерние по отношению к корневому узлу, после обмена элементов А [Ц и А [и] и уменьшения размера массива остаются невозрастающими, однако новый корневой элемент может нарушить свойство невозрастания пирамиды. Для восстановления этого свойства достаточно вызвать процедуру Млх НелР1Ру(А, 1), после чего подмассив А [1.. (и — 1)] превратится в невозрастающую пирамиду.
Затем алгоритм пирамидальной сортировки повторяет описанный процесс для невозрастающих пирамид размера и — 1, и — 2,..., 2. (См. упражнение 6.4-2, посвященное точной формулировке инварианта цикла данного алгоритма.) Нелгзокт(А) 1 Втг!ьп МЛХ НЕЛР(А) 2 1ог г — 1еидг)г[А] г1огтп1о 2 3 г1о Обменять А[1] + А[г] 4 Ьеар агге[А] — Ьеар згге[А] — 1 5 Млх Нелщгу(А,1) На рис. 6.4 показан пример пирамидальной сортировки после предварительного построения невозрастающей пирамиды. В каждой части этого рисунка изображена невозрастающая пирамида перед выполнением очередной итерации цикла 1ог в строках 2 — 5. В части а) этого рисунка показана исходная невозрастающая пирамида, полученная при помощи процедуры Вгльо Млх НелР.
В частях б) — «) показаны пирамиды, получающиеся в результате вызова процедуры Млх НелР1Рт в строке 5. В каждой из этих частей указано значение индекса г. В пирамиде содержатся толью узлы, закрашенные светло-серым цветом. В части л) показан получившийся в конечном итоге массив А. Время работы процедуры НелРеокт равно О (и18и), поскольку вызов процедуры Вгльо Млх Нели требует времени О(и), а каждый из и — 1 вызовов процедуры Млх НелР1Ру — времени О (18 и). УПРажНЕНИЯ 6.4-1. Используя в качестве модели рис.
6.4, проиллюстрируйте работу процедуры Н елгзокт с входным массивом А = (5, 13, 2, 25, 7, 17, 20, 8, 4). 6.4-2. Докажите корректность процедуры НелРзокт с помощью сформулированного ниже инварианта цикла. Глава 6. Пирамидальная сортировка 189 ):".) В Э' а) Ф ?3)) Э Э ЭФ Я ':;-':Ф. Ф ФЭФ л) й. ФЭ Э ЭЭЭ ж) Рис.
6.4. Работа процедуры НЕАР50кт В начале каждой итерации цикла 1ог в строках 2-5 подмассив А [1.Л] является невозрастающей пирамидой, содержащей г' наименьших элементов массива А [1..)т], а в подмассиве А [г + 1..п] находятся и — 1 отсортированных наибольших элементов массива А [1..п]. 6.4-3.
Чему равно время работы алгоритма пирамидальной сортировки массива А длины и, в котором элементы отсортированы и расположены в порядке возрастания? В порядке убывания? 6.4-4. Покажите, что время работы алгоритма пирамидальной сортировки в наихудшем случае равно Й(п!йп). * 6.4-5. Покажите, что для массива, все элементы которого различны, время работы пирамидальной сортировки в наилучшем случае равно й (г) 18 и). ® ЭЭФ (),, ФЭ® ))) ГМ' Ы Ф ФФ Ф ЭФЭ Часть Н. Сортировка и порядковая статистика 6.5 Очереди с приоритетами Пирамидальная сортировка — превосходный алгоритм, однако качественная реализация алгоритма быстрой сортировки, представленного в главе 7, на практике обычно превосходит по производительности пирамидальную сортировку.
Тем не менее, структура данных, использующаяся при пирамидальной сортировке, сама по себе имеет большую ценность. В этом разделе представлено одно из наиболее популярных применений пирамид — в качестве эффективных очередей с приоритетами. Как и пирамиды, очереди с приоритетами бывают двух видов: невозрастающие и неубывающие.
Мы рассмотрим процесс реализации невозрастаюших очередей с приоритетами, которые основаны на невозрастаюших пирамидах; в упражнении 6.5-3 требуется написать процедуры для неубывающих очередей с приоритетами. Очередь с приоритетами (рПогйу йпеое) — это структура данных, предназначенная для обслуживания множества о, с каждым элементом которого связано определенное значение, называющееся ключом (1сеу). В невозрастающей очереди с приоритетами поддерживаются следующие операции. ° Операция 1нзект(Я, х) вставляет элемент х в множество Я. Эту операцию можно записать как Я вЂ” Я 0 (х).
° Операция МАх!мам(Я) возвращает элемент множества о с наибольшим ключом. ° Операция ЕхтнАст МАх(Я) возвращает элемент с наибольшим ключом, удаляя его при этом из множества Я. ° Операция 1нснеАзе Кет(Я, х, )с) увеличивает значение ключа, соответствующего элементу х, путем его замены ключом со значением 1с.
Предполагается, что величина к не меньше текущего ключа элемента х. Одна из областей применения невозрастающих очередей — планирование заданий на иэмпьютере, который совместно используется несколькими пользователями. Очередь позволяет следить за заданиями, которые подлежат выполнению, и за их приоритетами. Если задание прервано или завершило свою работу, из очереди с помощью операции ЕхткАст МАх выбирается следующее задание с наибольшим приоритетом. В очередь в любое время можно добавить новое задание, воспользовавшись операцией НеАР 1мзект. В неубывающей очереди с лриоритетами поддерживаются операции 1нзект, Мпч|мым, ЕхткАст Мпч и ОескеАБе Кеу.
Очереди такого вида могут использоваться в моделировании систем, управляемых событиями. В роли элементов очереди в таком случае выступают моделируемые события, для каждого из которых сопоставляется время происшествия, играющее роль ключа. Элементы должны моделироваться последовательно согласно времени событий, поскольку Глава 6. Пирамидальная сортировка 191 процесс моделирования может вызвать генерацию других событий. Моделирующая программа выбирает очередное моделируемое событие с помощью операции ЕхткАс!' Мпч.
Когда инициируются новые события, они помещаются в очередь с помощью процедуры 1!чеект. В главах 23 и 24 нам предстоит познакомиться и с другими случаями применения неубывающих очередей с приоритетами, когда особо важной становится роль операции !3ескеАзе Кеу. Не удивительно, что приоритетную очередь можно реализовать с помощью пирамиды. В каждом отдельно взятом приложении, например, в планировщике заданий, или при моделировании событий элементы очереди с приоритетами соответствуют объектам, с которыми работает это приложение. Часто возникает необходимость определить, какой из обьектов приложения отвечает тому или иному элементу очереди, или наоборот.
Если очередь с приоритетами реализуется с помощью пирамиды, то в каждом элементе пирамиды приходится хранить идентификатор (Напсат!е) соответствующего обьекта приложения. То, каким будет конкретный вид этого идентификатора (указатель, целочисленный индекс или что-нибудь другое), — зависит от приложения. В каждом обьекте приложения точно так же необходимо хранить идентификатор соответствующего элемента пирамиды. В данной книге таким идентификатором, как правило, будет индекс массива. Поскольку в ходе операций над пирамидой ее элементы изменяют свое расположение в массиве, при перемещении элемента пирамиды необходимо также обновлять значение индекса в соответствующем объекте приложения. Так как детали доступа к объектам приложения в значительной мере зависят от самого приложения и его реализации, мы не станем останавливаться на этом вопросе.
Ограничимся лишь замечанием, что на практике необходима организация надлежащей обработки идентификаторов. Теперь перейдем к реализации операций в невозрастающей очереди с приоритетами, Процедура НеАР МАХ!м!!м реализует выполнение операции МАХ!м!!м за время !В (1): НБАР МАх!м!7м(А) ! ге!игл А[1] Процедура Недк ЕхткАст МАх реализует операцию ЕхткАст МАх.
Она напоминает тело цикла аког в строках 3-5 процедуры НеАРзокт: НеАР ЕхткАст МАх(А) 1 !балеар зие[А] < 1 2 !!зеп еггог "Очередь пуста" 3 тах А[1] 4 А[1] + — А[Авар зкзе[А]] 5 Беар змее[А] - Ьеар з!зе[А] — 1 6 МАх НеАР!РУ(А, 1) 7 гегпгп тат 192 Часть П. Сортировка и порядковая статистика Время работы процедуры Нвлг Ехтклст Млх равно О (1би), поскольку перед запуском процедуры Млх Нвлшгт, выполняющейся в течение времени О(1йи), в ней выполняется лишь определенная постоянная подготовительная работа. Процедура Нелг !мскелзв Кеу реализует операцию 1хскелзе Кву. Элемент очереди с приоритетами, ключ которого подлежит увеличению, идентифицируется в массиве с помощью индекса 1. Сначала процедура обновляет ключ элемента А (1].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
