Алгоритмы - построение и анализ (1021735), страница 37
Текст из файла (страница 37)
Поскольку это может нарушить свойство невозрастающих пирамид, после этого процедура проходит путь от измененного узла к корню в поисках надлежащего места для нового ключа. Эта операция напоминает реализованную в цикле процедуры 1мз витюша Яокт (строки 5-7) из раздела 2.1. В процессе прохода выполняется сравнение текущего элемента с родительским. Если оказывается, что ключ текущего элемента превышает значение ключа родительского элемента, то происходит обмен ключами элементов и процедура продолжает свою работу на более высоком уровне.
В противном случае процедура прекращает работу, поскольку ей удалось восстановить свойство невозрастающих пирамид. (Точная формулировка инварианта цикла этого алгоритма приведена в упражнении 6.5-5.) Нелг 1мсквлзв Кву(А,1, йеу) 1 11 1:еу < А[1] 2 гпеп еггог "Новый ключ меньше текущего" 3 А [1] — 1:еу згп1!е 1 > 1 и А(Рлкечт(1)] < А[1] сто Обменять А[1] А[рлкнчт(1)] 6 1 — Рлкечт(1) На рис. 6.5 приведен пример работы процедуры Нелг 1мснвлзд Кеу.
В части а этого рисунка изображена невозрастающая пирамида, в которой будет увеличен ключ узла, выделенного темно-серым цветом (кроме выделения цветом, возле этого узла указан индекс 1). В части б рисунка показана эта же пирамида после того, как ключ выделенного узла был увеличен до 15. В части в обрабатываемая пирамида изображена после первой итерации цикла зчЫ1е (строки 4 — 6). Здесь видно, как текущий и родительский по отношению к нему узлы обменялись ключами, и индекс 1 перешел к родительскому узлу. В части г показана эта же пирамида после еще одной итерации цикла. Теперь условие невозрастающих пирамид выполняется, и процедура завершает работу.
Время обработки и-элементной пирамиды с помощью этой процедуры равно О (1б и). Это объясняется тем, что длина пути от обновляемого в строке 3 элемента до корня равна О (1к и). Процедура Млх Нплг 1мзвпт реализует операцию 1мзект. В качестве параметра этой процедуре передается ключ нового элемента. Сначала процедура добавляет в пирамиду новый лист и присваивает ему ключ со значением — оо. Затем вызывается процедура Нелг 1мскелзе Кву, которая присваивает корректное зна- Глава 6.
Пирамидальная сортировка 193 гч ) у з ) / гг Рис. 6.5. Работа процедуры Нелв 1нскелзе Кет чение ключу и помещает его в надлежащее место, чтобы не нарушалось свойство невозрастающих пирамид: Млх НелР 1нзект(А, Йеу) 1 Беар згае[А[ — Беар згае[А[+ 1 2 А[йеар змее[А]) г — — оо 3 НЕЛР 1МСНЕЛБЕ КЕу(А,Беар згзе[А],йеу) Время вставки в гг-элементную пирамиду с помощью процедуры Млх Неле 1нзент составляет О (16 и). Подводя итог, заметим, что в пирамиде время выполнения всех операций по обслуживанию очереди с приоритетами равно О (16 и).
УПРажНЕНИЯ 6.5-1. Проиллюстрируйте работу процедуры Нелв Ехтнлст Млх с пирамидой А = (15, 13, 9, 5, 12, 8, 7, 4, О, 6, 2, 1). 6.5-2. Проиллюстрируйте работу процедуры Млх Нелв 1мзект(А., 10) с пирамидой А = (15,13,9,5,12,8,7,4,0,6,2,1). Воспользуйтесь в качестве модели рисунком 6.5. Часть й. Сортировка и порядковая статистика 194 6.5-3.
Напишите псевдокод процедур НелР М|ьпмим, Нелв Ехтклст Мщ Нелв Песпелзе Кеу и Мпч НелР 1нзепт, реализующих на базе неубывающей пирамиды неубывающую очередь с приоритетами. 6.5-4. Зачем нужна такая мера предосторожности, как присвоение ключу добавляемого в пирамиду узла в строке 2 процедуры Млх НелР 1хзект значения — оо, если уже при следующем шаге значение этого ключа увеличивается до требуемой величины? 6.5-5. Обоснуйте корректность процедуры Нелв 1~чспелзе Кеу с помощью следующего инварианта цикла. Перед каждой итерацией цикла ттЫ1е в строках 4-6, массив А [1.. Ьеар атяе [А]] удовлетворяет свойству невозрастающих пирамид, за исключением одного возможного нарушения— элемент А [1] может быть больше элемента А [РатеттФ (1)]. 6.5-6.
Покажите, как с помощью очереди с приоритетами реализовать очередь "первым вошел — первым вышел". Продемонстрируйте, как с помощью очереди с приоритетами реализовать стек. (Очереди и стеки определены в разделе 10.1.) 6.5-7. Процедура НелР Редеете(А, 1) удаляет из пирамиды А узел г.
Разработайте реализацию этой процедуры, которой требуется время О (1к и) для удаления узла из и-элементной невозрастающей пирамиды. 6.5-В. Разработайте алгоритм„объединяющий )с отсортированных списков в один список за время О (и 1я 1с), где и — общее количество элементов ао всех входных списках. (Указание: для слияния списков воспользуйтесь неубывающей пирамидой.) Задачи 6-1. Создание пирамиды с помощью вставок Описанную в разделе 6.3 процедуру Втал Млх НелР можно реализовать путем многократного использования процедуры Млх НелР 1нзект для вставки элементов в пирамиду.
Рассмотрим следующую реализацию: Вцпл Млх НелР'(А) 1 Ьеар атее[А] — 1 2 Гог г' — 2 1о 1еидй[А] 3 бо Млх НелР 1мзепт(А, А[1]) а) Всегда ли процедуры Вин.п Млх НелР и Вин.п Млх НелР/ для одного и того же входного массива создают одинаковые пирамиды? Докажите, что это так, или приведите контрпример. Глава 6. Пирамидальная сортировка б) Покажите, что в наихудшем случае для создания и-элементной пи- рамиды процедуре Вий.п Млх Нвлкг требуется время 9 (п1яп). 6-2. Анализ пирамид, отличных от бинарных Ы-арные пирамиды (6-агу Беар) похожи на бинарные, с тем исключением, что узлы, отличные от листьев, имеют не по 2, а по д дочерних элементов.
а) Как бы вы представили а-арную пирамиду в виде массива? б) Как выражается высота Н-арной и-элементной пирамиды через п и д? в) Разработайте эффективную реализацию процедуры Ехтклст Млх, предназначенную для работы с Н-арной невозрастающей пирамидой. Проанализируйте время работы этой процедуры и выразите его в терминах и' и и. г) Разработайте эффективную реализацию процедуры 1нзвкт, предназначенную для работы с Н-арной невозрастающей пирамидой. Проанализируйте время работы этой процедуры и выразите его в терминах 6 и п. д) Разработайте эффективную реализацию процедуры 1мскнлзн Кну(А,(, й), в которой сначала выполняется присвоение А [1] +- +- шах(А [1], 1с), а затем — обновление а-арной невозрастающей пирамиды.
Проанализируйте время работы этой процедуры и выразите его в терминах и' и и. 6-3. Таблицы Юнга Таблица Юнга (г'оипб 1аЫеап) т х п — это матрица т х п, элементы которой в каждой строке отсортированы слева направо, а в каждом столбце — сверху вниз. Некоторые элементы таблицы Юнга могут быть равны оо, что трактуется как отсутствие элемента. Таким образом, в таблице Юнга можно разместить т < тп конечных чисел. а) Начертите таблицу Юнга 4 х 4, содержащую элементы (9, 16, 3, 2, 4, 8, 5, 14, 12). б) Докажите, что таблица Юнга У размером т х п пустая, если У [1, 1] = со. Докажите, что таблица У полностью заполнена (т.е.
она содержит тп элементов), если У [т, и] < со. в) Разработайте алгоритм, реализующий процедуру Ехтклст Мпч для непустой таблицы Юнга т х п за время 0(т+ и). В алгоритме следует использовать рекурсивную подпрограмму, которая решает задачу размером т х п путем рекурсивного сведения к задачам (т — 1) х п или т х (и — 1). (Указание: вспомните о процедуре 196 Часть П. Сортировка и порядковая статистика Млх Нихшгу.) Обозначим максимальное время обработки произвольной таблицы Юнга т х и с помощью процедуры Ехтклст Мп~ как Т (р), где р = т + и.
Запишите и решите рекуррентное соотношение, которое дает границу для Т(р), равную О (т+ и). г) Покажите, как вставить новый элемент в незаполненную таблицу Юнга размером т х п за время О (т + и). д) Покажите, как с помощью таблицы Юнга и х п выполнить сортировку пз чисел за время О [пз), не используя при этом никаких других подпрограмм сортировки. е) Разработайте алгоритм, позволяющий за время О [т + п) определить, содержится ли в таблице Юнга размером т х п заданное число. Заключительные замечания Алгоритм пирамидальной сортировки был предложен Вильямсом (МП1ашз) [316], который также описал, каким образом с помощью пирамиды можно реализовать очередь с приоритетами.
Процедура Впьо Млх Ннлк разработана Флойдом (Р[оуб) [90]. В главах 16, 23 и 24 будут реализованы очереди с приоритетами с помощью неубывающих пирамид. В главах 19 и 20 вы познакомитесь с реализацией некоторых операций с улучшенными временными характеристиками. Для целочисленных данных можно реализовать очереди с приоритетами, работающие быстрее, чем те, в которых не делаются предварительные предположения о типе данных. В структуре данных, предложенной Боасом (чап ЕпЫе Воаз) [301], поддерживаются операции Мммим, Млх|мим, 1мзвкт, 13н.итв, Бвхксн, Ехтклст Мпч, Ехтклст Млх, Ркеэесиззок и Яиссиззск.
При условии, что ключи выбираются из множества [1, 2,..., С), время работы этих операций в наихудшем случае оценивается как О (1к 1кС). Фредман (Ргейпап) и Виллард (М!1ап1) [99] показали, как реализовать операцию Мммим со временем работы О(1) и операции 1ювкт и Ехтклст Мпч со временем работы О [~([б п), если данные представляют собой 6-битовые целые числа, а память компьютера состоит из адресуемых 6-битовых слов.
В работе Торупа (ТЬогпр) [299] граница О [~Лд и) была улучшена до О (1к 1к п). При этом используемая память не ограничена величиной п, однако такого линейного ограничения используемой памяти можно достичь с помощью рандомизированного хеширования. Важный частный случай очередей с приоритетами имеет место, когда последовательность операций Ехтклст Мпч является монотонной, т.е. возвращаемые этой операцией последовательные значения образуют монотонную возрастающую Глава б. Пирамидальная сортировка 197 последовательность.
Такая ситуация встречается во многих важных приложениях, например, в алгоритме поиска кратчайшего пути Дейкстры (01)кмга), который рассматривается в главе 24, и при моделировании дискретных событий. Для алгоритма Дейкстры особенно важна эффективность операции Пнскназн Кку. Для частного случая монотонности для целочисленных данных из диапазона 1, 2, ..., С, Ахуйя (АЬп)а), Мельхорн (МеЬ1Ьогп), Орлин (Ог!1п) и Таржан (Таг)ан) [8) описали, как с помощью структуры данных под названием позиционная пирамида (гайх Ьеар) реализовать операции Ехтклст М[м и 1мзнкт со временем выполнения 0 (18 С) (более подробные сведения на эту тему можно найти в главе 17), и операцию 1)нскнлзн Кнт со временем выполнения 0 (1). Граница 0 (18 С) может быть улучшена до 0 [~48 С) путем совместного использования пирамид Фибоначчи (см. главу 20) и позиционных пирамид.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
