Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 40
Текст из файла (страница 40)
В качестве параметра этой процедуре передается ключ нового элемента, вставляемого в невозрастающую пирамиду А. Сначала процедура добавляет в пирамиду новый лист и присваивает ему ключ со значением — оо. Затем вызывается процедура НКАР1хскеАБе-Кеу, которая присваивает корректное значение ключу нового узла и помещает его в надлежащее место, чтобы не нарушалось свойство невозрастающей пирамиды. ?94 Часть ЕС Сортировка и порядковая статистика 6.5.3 Напишите псевдокоды процедур Нели-М|н1мпм, Нелр-Ехтилст-Мпч, НелгПескеАее-Кеу и М1м-Нелр-1мзеет, реализующих неубывающую очередь с приоритетами на базе неубывающей пирамиды. 6.5.4 Зачем нужна такая мера предосторожности, как присвоение ключу добавляемого в строке 2 процедуры МАх-НеАЕ-1мзее г в пирамиду узла значения — оо, если уже на следующем шаге значение этого ключа увеличивается до требуемой величины? 6.5.5 Докажите корректность процедуры НеАЕ-1мскеАее-Кеу с помощью следующего инварианта цикла, В начале каждой итерации цикла зиЫ1е в строках 4-6 А[РАкент(1)] ) А[1.еет(1)] и А[РАкент(1)] > А[Ксилит(г)], если эти узлы существуют, а подмассив А[1..
А.)ьеар-вше] удовлетворяет свойству невозрастающей пирамиды, за исключением, возможно, одного нарушения: А[1] может быть больше, чем А[РАЕЕХТ(1)]. Можно считать, что в момент вызова процедуры НеАР-1хскеАБе-Кеу подмас- сив А[1 .. А. Ьеар-вие] удовлетворяет свойству невозрастающей пирамиды. 6.5.6 Каждая операция обмена в строке 5 процедуры НЕАР-1ЯСЕЕАБЕ-КЕу обычно требует трех присваиваний.
Покажите, как воспользоваться идеей внутреннего цикла процедуры 1НЗЕКт1ОН-БОКт, чтобы вместо трех присваиваний обойтись только одним. 6.5. 7 Покажите, как с помощью очереди с приоритетами реализовать очередь "первым вошел — первым вышел". Продемонстрируйте, как с помощью очереди с приоритетами реализовать стек. (Очереди и стеки определены в разделе 10.1.) 6.5.8 Процедура НеАР-Песете(А,1) удаляет из пирамиды А узел 1. Разработайте реализацию этой процедуры, которой требуется время 0(1я и) для удаления узла из п-элементной невозрастающей пирамиды. 6.5. 9 Разработайте алгоритм, объединяющий к отсортированных списков в один список за время 0(п1я/с), где и — общее количество элементов во всех входных списках. (Указаниес для слияния списков воспользуйтесь неубывающей пирамидой.) 195 Глава д Пиаттлтьиая сортировка Задачи 6.1.
Построение лирамиды оголовками Пирамиду можно построить с помощью многократного вызова процедуры МАХ-НеАР-1!чзект для вставки элементов в пирамиду. Рассмотрим следующий вариант процедуры Вппл)-МАХ-НеАР. В0!еп-МАх-НеАР (А) ! А.Ьеар-веге = 1 2 1ог 1 = 2 Го А. 1еид16 3 МАх-НеАР-1!чхект(А, А[1)) а Всегда ли процедуры В!5!еп-МАХ-НеАР и В!леп-МАХ-НеАР' для одного и того же входного массива создают одну и ту же пирамиду? Докажите, что это так, или приведите коитрпример. й Покажите, что в наихудшем случае для создания и-элемеитиой пирамиды процедуре В!5и.п-МАХ-НеАР потребуется время б!(и 1я и).
6.3. Аиаанэ И ариых лирамид лд араме пирамиды подобны бинарным, ио отличаются тем, что все внутренвие узлы (с одним возможным исключением) имеют вместо двух Ы дочерних узлов. а Как бы вы представили 4-ариую пирамиду в виде массива? 6. Как выражается высота л?-арией и-элемептиой пирамиды через и и И? в. Разработайте эффективную реализацию процедуры ЕхткАст-МАХ, предиазиачеииую для работы с л1-арией иевозрастающей пирамидой. Проаиализируйте время работы этой процедуры и выразите его через д и и. г.
Разработайте эффективную реализацию процедуры 1!чзект, предназначенную для работы с 6-арией иевозрастающей пирамидой. Проанализируйте время работы этой процедуры и выразите его через 6 и и. д. Разработайте эффективную реализацию процедуры 1мскеАзе-Кеу(А,л,lс), которая при а ( А[1] сообщает об ошибке, а в противном случае выполияет присваиваиие А[1[ = )с и соответствующим образом обновляет структуру И-арией иевозрастающей пирамиды.
Проанализируйте время работы этой процедуры и выразите его через л? и и. 6.3. Таблицы Юнга Таблица Юнга (Топай !аЫеап) ги х и представляет собой матрицу размером т х и, злемеиты которой в каждой строке отсортироваиы слева направо, а в каж- 19б Часть П. Сортировка и оорвдковак статистика дом столбце — сверху вниз. Некоторые элементы таблицы Юнга могут быть равны оо, что трактуется как отсутствие элемента. Таким образом, таблицу Юнга можно использовать для хранения т < тпп конечных чисел. в. Начертнте таблицу Юнга 4 х 4, в которой содержатся элементы (9, 16, 3, 2, 4, 8.
5, 14, 12). б. Докажите, что таблица Юнга У размером т х п пуста, если У[1,1] = сс. Докажите, что таблица У полностью заполнена (т.е. содержит гпп элементов), если У[т,и] с оо. в. Разработайте алгоритм, реализующий процедуру Ехтклст-Мпч для непустой таблицы Юнга т х и за время 0(т + и). В алгоритме следует использовать рекурсивную подпрограмму, которая решает задачу размером гп х и путем рекурсивного сведения к задачам (т — 1) х п или т х (и — 1).
(Указание: вспомните о процедуре МАх-НлА91ру.) Обозначим максимальное время обработки произвольной таблицы Юнга т х п с помощью процедуры ЕХТКАСт-М1Н как Т(р), где р = гп+ и. Запишите и решите рекуррентное соотношение, которое дает для Т(р) границу 0(т + п). а Покажите, как вставить новый элемент в незаполненную таблицу Юнга размером т х и за время 0(т + п). д.
Покажите, как с помощью таблицы Юнга п х п выполнить сортировку пз чисел за время 0(п ), не используя при этом никаких других подпрограмм сортировки. в. Разработайте алгоритм, позволяющий за время 0(т+ и) определить, содержится ли в таблице Юнга размером т х и заданное число. Заключительные замечания Алгоритм пирамидальной сортировки был разработан Вильямсом (%'!!!!ашз) [355], который также описал, каким образом с помощью пирамиды можно реализовать очередь с приоритетами. Процедура Вп!сп-МАх-Нцлр предложена Флойдом (Р!оуб) (105]. В главах 16, 23 и 24 неубывающие пирамиды будут использованы для реализации неубывающих очередей с приоритетами. В главе 19 будет представлена реализация с улучшенными временными границами, а в главе 20 — усовершенствованная реализация для случая, когда ключи выбираются иэ ограниченного множества неотрицательных целых чисел. Для случая, когда данные представляют собой Ь-битовые целые числа, а память компьютера состоит из адресуемых Ь-битовых слов, Фредман (Ргебшал) и Уиллард (1й!!!аго) (114] показали, как реализовать процедуру М11ч1мпм со временем работы 0(1) и процедуры 1нзект и ЕхткАст-М[ы со временем работы Глава б.
Пираиидальиаа сартиравка 797 О( Яп). Торуп (ТЬогцр) [335] улучшил границу 0(ч7Г8 и) до 0(1818п). При этом используемая память не ограничена величиной и, однако такого линейного ограничения используемой памяти можно достичь с помощью рандомизированного хеширования. Важный частный случай очередей с приоритетами имеет место, когда последовательность операций ЕхткАст-Мгм является монотонной, т.е. возвращаемые последовательными операциями ЕхткАст-МП4 значения образуют монотонно неубывающую последовательность.
Такая ситуация встречается во многих важных приложениях, например в алгоритме поиска кратчайшего пути Дейкстры (Р1]кзгга), который рассматривается в главе 24, или при моделировании дискретных событий. Для алгоритма Дейкстры особенно важна эффективность реализации операции РесккАзк-Клч. Для частного случая монотонности для целочисленных данных из диапазона 1,2,...,С Ахуйя (АЬц]а), Мельхорн (Мей(йопэ), Орлин (Ог!ш) и Таржан (Таг]ап) [8] описали, как с помощью структуры данных под названием "позиционная пирамида" (гагйх Ьеар) реализовать операции Ехтклст-Мпв и 174зцкт с амортизированным временем работы 0(18С) (более подробные сведения на эту тему можно найти в главе 17) и операцию Рксккхзк-Кеч со временем работы 0(1). Граница 0(18С) может быть улучшена до 0(ч7187,') путем совместного использования пирамид Фибоначчи (см.
главу 19) и позиционных пирамид. Дальнейшее улучшение этой границы до 0(18'7з+в С) было осуществлено Черкасски (СЬегказзку), Гольдбергом (Оо)ОЬегй) и Сильверстайном (%1чегзгеш) [64], которые обьединили многоуровневую груплирующую структуру (пш!й-1ече! Ьцс1се6пй з1гцсшге) Денардо (Репагбо) и Фокса (Рох) [84] с уже упоминавшейся пирамидой Торупа. Раману (йашап) [289] удалось еще больше улучшить эти результаты и получить границу, которая равна 0(ппп(18'74+' С, 18'7з+' и)) для произвольной фиксированной величины 4 > О.
Глава 7. Быстрая сортировка Алгоритм быстрой сортировки имеет в наихудшем случае для входного массива из и элементов время работы, равное 9(пз). Несмотря на такую медленную работу в наихудшем случае, этот алгоритм на практике зачастую оказывается оптимальным благодаря тому, что в среднем время его работы намного лучше: 6(п 1к и).
Кроме того, постоянный множитель, скрытый в выражении 6(п 1к и), достаточно мал по величине. Алгоритм обладает также тем преимуществом, что сортировка в нем выполняется на месте, без использования дополнительной памяти (см. с. 39), поэтому он хорошо работает даже в средах с виртуальной памятью. В разделе 7.1 описаны сам алгоритм и важная подпрограмма, использующаяся в нем для разбиения массива. Поскольку поведение алгоритма быстрой сортировки достаточно сложное, мы начнем с нестрогого„интуитивного обсуждения производительности этого алгоритма в разделе 7.2, а строгий анализ отложим до конца данной главы.
В разделе 7,3 представлена версия быстрой сортировки, в которой используется случайная выборка. У этого алгоритма хорошее ожидаемое время работы, при этом никакие конкретные входные данные не могут ухудшить его производительность до уровня наихудшего случая. Этот рандомизнрованный алгоритм анализируется в разделе 7А, где показано, что время его работы в наихудшем случае равно Э(пз), а среднее время работы в предположении, что все элементы различны, составляет 0(п!ли). 7.1. Описание быстрой сортировки Быстрая сортировка, подобно сортировке слиянием, применяет парадигму "разделяй и властвуй", представленную в разделе 2.3.1.
Ниже описан процесс сортировки подмассива А[р .. г), состоящий, как и все алгоритмы с использованием декомпозиции, из трех этапов. Разделение. Массив А[р .. г[ разбивается на два (возможно, пустых) подмассива А [р .. о — Ц и А [д+ 1 .. г1 таких, что каждый элемент А [р .. о — Ц меньше или равен А[з], который, в свою очередь, не превышает любой элемент подмассива А[д + 1 .. г[, Индекс д вычисляется в ходе процедуры разбиения. 799 Глава 7.
Быслираи сортировка Властвование. Подмассивы А[р .. ц — 1] и А[4 + 1 .. т[ сортируются с помощью рекурсивного вызова процедуры быстрой сортировки. Комбинирование. Поскольку подмассивы соргируются на месте, для их объединения не требуются никакие действия: весь массив А[р..т] оказывается отсортированным. Быстрая сортировка реализуется следующей процедурой, Япскзокт(А, р, т) ! !Гр<т 2 д = Рлкт!тюм(А,р,т) 3 Оо!скзокт(А, р, о — 1) 4 ОГ71СКЗОКт(А,д+ 1,т) Для сортировки всего массива А начальный вызов процедуры должен иметь вид Орлскзокт(А, 1, А.
!еп9Ф). Разбиение массива Ключевой частью рассматриваемого алгоритма сортировки является процедура РЛКт1т!О1Ч, изменяющая порядок элементов подмассива А[р .. т] без привлечения дополнительной памяти. Рлкт1т!он(А Р т) 1 х=А[т] 2 !кр — 1 3 !ог 7' = р Го т — 1 4 !г" А[7] < х 5 1=!+1 6 Обменять А[!] и А[7'] 7 Обменять А[1+ 1] и А[т! 8 гегнгв 1+ 1 На рис. 7. ! показано, как процедура Рлкт1тю!ч работает с 8-элементным массивом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
