Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 39
Текст из файла (страница 39)
Время работы процедуры МАх-Нилг1гу при ее вызове для работы с узлом, который находится на высоте Ь, равно 0(Ь), так что общая стоимость процедуры ВО1ЬП-МАХ-НиАГ ограничена сверху значением 11к а) 11к а) ~ ~ — „"„10(А) =0 а=о а=о Последняя сумма вычисляется путем подстановки х = 1/2 в формулу (А.8), что дает Ь 1/2 2ь (1 — 1~2)з = 2. Таким образом, время работы процедуры Вщ1.п-МАХ-НЕАР имеет верхнюю гра- ницу 0 и ~~~ — „=0 п~ = 0(п) .
Следовательно, построить невозрастающую пирамиду из неупорядоченного массива можно за линейное время. Неубывающая пирамида строится с помощью процедуры Вин.п-Мпч-Неяг, идентичной процедуре Впп.п-МАх-НвАг, лишь вызов Млх-Нвлшгт в строке 3 заменяется вызовом Мпч-Нвлшгт (упр. 6.2.2). Процедура Впшп-М1м-НвАг строит неубывающую пирамиду из неупорядоченного массива за линейное время. Часть ГЕ Сортирокка и яоряаковая статистика Ио Упражнения 6.3.1 Воспользовавшись в качестве образца рнс. 6.3, проиллюстрируйте работу процедуры ВО!1п-МАх-НеАР над входным массивом А = (5, 3, 17, 10,84, 19,6, 22,9).
б.3.2 Почему индекс цикла ! в строке 2 процедуры ВО!ЕО-МАХ-НеАР убывает от [А. 1епд!Ь/2] до 1, а не возрастает от 1 до [А. 1епд!Ь/2]? 6.3.3 Покажите, что в любой п-элемеитной пирамиде на высоте Ь находится не более [п/2"+'] узлов. 6.4. Алгоритм пирамидальной сортировки Работа алгоритма пирамидальной сортировки начинается с вызова процедуры ВО!еп-МАХ-НеАР для построения невозрастаюшей пирамиды из входного массива А[1 ..
и], где п = А.1епд!Ь. Посюльку наибольший элемент массива находится в юрие А[1], его можно поместить в корректную окончательную позицию в отсортированном массиве, поменяв его местами с элементом А[п]. Выбросив из пирамиды узел и (путем уменьшения на единицу величины А. Ьеар-я!яе, мы обнаружим, что дочерние поддеревья корня остаются корректными невозрастающими пирамидами, и только корень может нарушать свойство невозрастающей пирамиды. Для восстановления этого свойства достаточно вызвать процедуру МАХ-НеАР! Ру (А, 1), после чего подмассив А[1 .. и — 1] превратится в невозрастаюшую пирамиду.
Затем алгоритм пирамидальной сортировки повторяет описанный процесс для невозрастаюших пирамид размером от п — 1 до 2. (См. упр. 6.4.2, посвященное точной формулировке инварианта цикла данного алгоритма.) НЕАРЯОКТ(А) 1 В!!!еп-МАх-НеАР(А) 2 Гогз = А.1епд!Ь дозгпьо 2 3 Обменять А[1] с А[1] 4 А. Ьеар-я!се = А. Ьеар-ягае — 1 5 МАХ-НЕАР!РЧ(А, 1) На рис. 6.4 приведен пример работы процедуры НЕАРЕОХТ, после того как в строке 1 была построена начальная невозрастаюшая пирамида. На рисунке показана невозрастаюшая пирамида перед первой итерацией цикла Кот в строках 2 — 5 и после каждой из итераций.
Время работы процедуры НЕАРЕОКТ равно 0(и 18п), посюльку вызов процедуры ВО!еп-МАХ-НеАР требует времени О(п), а каждый из п — 1 вызовов процедуры МАх-НеАшгч — времени 0(18 и). Ир Глава и Пирамидальная сор)лироаяа ) 'т; )41:,)' (2.: ((; ф ( (з'; ф ф (а) (а) (в) :.9'; ьа( !71 4':7. ()~ ~з, „4,)~ ))' (ф;), )() фг ф (а) (г) (з) (и) (н) А ) ~"Я 1 3" (14: гу)т з '[р::)о„, )4)46, ффф Рис. 6.4. Рабата процедуры Неявзокт (в) Невозрастаюшая пирамида сразу после построения пропслурой Вшьо-Мах-Нанн в строке 1. (4)-(н) Невозрастаюшая пирамида после каилого вылова Мах-Нвлмвт а строке 5; указано также значение з в этот момент.
В невозрастаюшей пирнаиле остаются только свеппае узлы. (л) Выходной отсортированный массив А. Управ(ненни (ь41 Воспользовавшись в качестве образца рис. 6.4, проиллюстрируйте работу процедуры Нпдрзокт над входным массивом А = (5,13,2,25,7,17,20,8,4). ыг Докажите корректность процедуры Нилрзокт с помощью следующего инварианта цикла. В начале каждой итерации цикла (ог в строках 2-5 подмассив А[1..)] представляет собой невозрастающую пирамиду, содержащую т наименьших элементов массива А[1 .. п], а в подмассиве А[а+1 .. и] содержатся и — з наибольших элементов массива А[1 ..
и] в отсортированном состоянии. Часть Гь' Сортировка и яорядковая статистика б.4.3 Чему равно время работы процедуры Нпкрзокт с массивом А длиной п, в котором элементы отсортированы и расположены в порядке возрастания? В порядке убывания? б.4.4 Покажите, что время работы процедуры Ннлрзокт в наихудшем случае составляет Й(п 1я и). 4.4.5 * Покажите, чзо, когда все элементы различны, время работы процедуры Нпкрзокт в наилучшем случае равно Й(п 1я и). 6.5. Очереди с приоритетами Пирамидальная сортировка — превосходный алгоритм, однако качественная реализация алгоритма быстрой сортировки, представленного в главе 7, на практике обычно превосходит по производительности пирамидальную сортировку.
Тем не менее структура данных, использующаяся при пирамидальной сортировке, сама по себе имеет множество применений. В этом разделе представлено одно из наиболее популярных применений пирамид — в качестве эффективных очередей с приоритетами. Как и пирамиды, очереди с приоритетами бывают двух видов; невозрастающне и неубывающие. Мы рассмотрим процесс реализации невозрастающих очередей с приоритетами, которые основаны на невозрастающих пирамидах; в упр. 6.5.3 требуется написать процедуры для неубывающих очередей с приоритетами. Очередь с приоритетами (рпопГу Члене) представляет собой структуру данных, предназначенную для обслуживания множества Я, с каждым элементом которого связано определенное значение, называющееся ключом (1геу).
В неаазрастающей очереди с приоритетами поддерживаются следующие операции. 1хзект(э,х) вставляет элемент х в множество э, что эквивалентно операции 5 = Зи(х). Мхх|мсм(Я) возвращает элемент множества В с наибольшим ключом, Ехткхст-Мах(о) удаляет и возвращает элемент множества Я с наибольшим ключом. 1нсднАзн-Кну (Я, х, й) увеличивает значение ключа элемента х до нового значения к, которое предполагается не меньшим значения текущего ключа элемента х. Среди прочих областей применения невозрастающих очередей — планирование заданий на совместно используемом компьютере. Очередь позволяет следить за заданиями„которые подлежат выполнению, и за их относительными приоритетами.
Если задание прервано илн завершило свою работу, планировщик выбирает !91 Глава б. Пираиидальлал сортировка из очереди с помощью операции Ехтклст-Млх следующее задание с наибольшим приоритетом. В очередь в любое время можно добавить новое задание, воспользовавшись операцией 1нзект. Аналогично в неубывающей очереди с приоритетама поддерживаются операции 1ызект, Мпв!мам, Ехтклст-М!гв и 13ескелзе-Кеу. Очереди этого вида могут использоваться в моделировании систем, управляемых событиями.
В роли элементов очереди в таком случае выступают моделируемые события, для каждого из которых сопоставляется время осуществления, играющее роль ключа. События должны моделироваться последовательно, согласно времени их наступления, поскольку процесс моделирования может вьжвать генерацию других событий, которые нужно будет моделировать позже. Моделирующая программа выбирает очередное моделируемое событие с помощью операции Ехтклст-Мпч. Когда инициируются новые события, они помещаются в очередь с помощью процедуры 1нзект. В главах 23 и 24 нам предстоит познакомиться и с другими случаями применения неубывающих очередей с приоритетами, когда особо важной становится роль операции Оескелзе-Кеу.
Не удивительно, что приоритетную очередь можно реализовать с помощью пирамиды. В каждом отдельно взятом приложении, например в планировщике заданий, или при моделировании событий элементы очереди с приоритетами соответствуют объектам, с которыми работает это приложение. Часто возникает необходимость определить, какой из объектов приложения отвечает тому или иному элементу очереди, или наоборот. Если очередь с приоритетами реализуется с помощью пирамиды, то в каждом элементе пирамиды приходится хранить идентификатор (!эаш)!е) соответствующего обьекта приложения. То, каким будет конкретный вид этого идентификатора (таким, как указатель или целочисленный индекс), зависит от приложения.
В каждом объекте приложения точно так же необходимо хранить идентификатор соответствующего элемента пирамиды. В данной книге таким идентификатором, как правило, будет индекс массива. Поскольку в ходе операций над пирамидой ее элементы изменяют свое расположение в массиве, при перемещении элемента пирамиды необходимо также обновлять значение индекса в соответствующем объекте приложения. Так как детали доступа к объектам приложения сильно зависят от самого приложения и его реализации, мы не станем останавливаться на этом вопросе.
Ограничимся лишь замечанием, что на практике необходима организация надлежащей обработки идентификаторов. Теперь рассмотрим, как реализовать операции в невозрастающей очереди с приоритетами. Процедура Нелг-Млх!мам реализует операцию Млх!мам за время Й(1). Не лР-Млх!мпм (А) 1 гегпгп А!1] Процедура Нелг-Ехтклст-Млх реализует операцию Ехтклст-Млх. Она похожа на тело цикла 1ог (строки 3 — 5) процедуры НЕлРЗОКт. 192 Часть РЕ Сортировка и яорядковая статистика НЕАР-ЕХТКАСТ-МАХ (А) 1 1ГА.Ьеар-ваке < 1 2 еггог "Очередь пуста'" 3 так = А[1] 4 А[1] = А[А.Беар-в!ге] 5 А.!ьеар-вгае = А,!ьеар-агае — 1 6 МАХ-НЕАР1РУ (А, 1) 7 ге!игл тат Время работы процедуры НеАР-ЕхткАст-МАх равно 0(1я и), поскольку она выполняет только константное количество работы перед вызовом процедуры МАхНЕАР1РТ, время работы которой — О(!я и).
Процедура НеАР-!хскеязе-Кеу реализует операцию 1хскеАзе-Кеу. Элемент очереди с приоритетами, ключ которого подлежит увеличению, идентифицируется в массиве с помощью индекса Е Сначала процедура обновляет ключ элемента А[!]. Поскольку это действие может нарушить свойство невозрастающей пирамиды, после этого процедура проходит путь от измененного узла к корню в поисках надлежащего места для нового ключа. Эта операция напоминает операцию, реализованную в цикле процедуры 1ХЕЕКТ1оХ-Бокт из раздела 2.1 (строки 5-7). В процессе прохода выполняется сравнение текущего элемента с родительским. Если оказывается, что ключ текущего элемента превышает значение ключа родительского элемента, то происходит обмен ключами элементов и процедура продолжает свою работу на более высоком уровне.
В противном случае процедура прекращает работу, поскольку ей удалось восстановить свойство невозрастающих пирамид. (Точная формулировка соответствующего инварианта цикла приведена в упр. 6.5.5.) НЕАР-1ХСКЕАБЕ-КЕУ(А, 1, )сеу) 1 !1 лисеу < А[1] 2 еггог "Новый ключ меньше текущего" 3 А[1] = lсеу 4 эгп!!е ! > 1 и А[РАкехт(1)] < А[!] 5 Обменять А[!] и А[РАКЕХТ(!)] 6 ! = РАКЕХТ(!) На рис.6.5 показан пример выполнения операции НКАР-1хскеязе-Кеу. Время работы процедуры НКАР-1хскеАзе-Кеу над и-элементной пирамидой равно О(!ни), поскольку путь от обновляемого в строке 3 узла до корня имеет длину О(!к и). Процедура МАХ-НКАР-1хзект реализует операцию 1хзект.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
