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