Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 37
Текст из файла (страница 37)
Завершение. После завершения цикла г = О. В соответствии с инвариантом цикла, все узлы с индексами 1, 2,..., п являются корнями невозрастающих пирамид. В частности, таким корнем является узел 1. Простую верхнюю оценку времени работы процедуры Вшпп МАх НеАР можно получить следующим простым способом. Каждый вызов процедуры МАх НеАйгу занимает время О (18п), и всего имеется О (и) таких вызовов.
Таким образом, время работы алгоритма равно О (п!бп). Эта верхняя граница вполне корректна, однако не является асимптотически точной. Чтобы получить более точную оценку, заметим, что время работы МАх Нелигу в том или ином узле зависит от высоты этого узла, и при этом большинство узлов расположено на малой высоте. Прн более тщательном анализе принимается во внимание тот факт, что высота п-элементной пирамиды равна (18п) (упражнение 6.1-2) и что на любом уровне, находящемся на высоте й, содержится не более ~п/2ь+~~ узлов (упражнение 6.3-3).
Время работы процедуры МАх Нелигу при ее вызове для работы с узлом, который находится на высоте Ь, равно О (л), поэтому верхнюю оценку полного времени работы процедуры Впшп МАХ НЕАР можно записать следующим Глава 6. Пирамидальная сортировка 187 образом: Ря ь) Рв п) Е [' —,"„,1О(8)=О пŠ— ", а=а л=о Сумму в последнем выражении можно оценить, подставив з = 1/2 в формулу (А.8), в результате чего получим: 6 1/2 = 2. ( - /2)' Таким образом, время работы процедуры Вгльп Млх Нилг можно ограничить следующим образом: О п ~~> — „=О п~ — „=О(п).
Получается, что время, которое требуется для преобразования неупорядоченного массива в невозрастающую пирамиду, линейно зависит от размера входных данных. Неубывающую пирамиду можно создать с помощью процедуры Вцп.п Мпч Нплг, полученной в результате преобразования процедуры Вгльп Млх Нклг путем замены в строке 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 Часть П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
