Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 38
Текст из файла (страница 38)
Свайства неубывающих пирамид (ппп-Ьеар ргорепу) заключается в том, что для всех отличных от корневого узлов с индексом 1 выполняется неравенство А[РАКЕХТ(г)] < А[1] . Таким образом, наименьший элемент такой пирамиды находится в ее корне. В алгоритме пирамидальной сортировки используются невозрастающие пирамиды. Неубывающие пирамиды часто реализуют очереди с приоритетами (этот вопрос обсуждается в разделе 6.5).
Для каждого приложения будет указано, с пирамидами какого вида мы будем иметь дело — с неубывающими или невозрастающими. При описании свойств, общих как для неубывающих, так и для невозрастающих пирамид, будет использоваться общий термин "пирамида". Рассматривая пирамиду как дерево, определим высоту ее узла как число ребер в самом длинном простом нисходящем пути от этого узла к какому-то из листьев дерева. Высота пирамиды определяется как высота ее корня. Поскольку и-элементная пирамида строится по принципу полного бинарного дерева, ее высота равна 9(1к п) (см.
упр. б.1.2). Мы увидим, что время выполнения основных операций в пирамиде приблизительно пропорционально высоте дерева, и, таким образом, эти операции требуют для работы время О(1к и). В остальных разделах этой главы представлено несколько базовых процедур и продемонстрировано их использование в алгоритме сортировки и в структуре данных очереди с приоритетами. Процедура МАх-НЕАщру выполняется за время 0(1яп) и служит для под- держки свойства невозрастания пирамиды.
Время выполнения процедуры Вгггьп-МАх-НЕАР увеличивается с ростом количества элементов линейно. Эта процедура предназначена для создания невозрастающей пирамиды из неупорядоченного входного массива. Процедура НЕАРЗОКТ выполняется за время 0(п 1к и) и сортирует массив без привлечения дополнительной памяти. Процедуры МАх-НеАР-1мзект, НеАР-Ехтклст-МАх, НеАР-1мскелзе-Кеу н НеАР-МАхгмьгм выполняются за время 0(1кп) и позволяют использовать пирамиду для реализации очереди с приоритетами.
Часть Е!. Сортировка и яорядковая статистика Упражнения 6.1.1 Чему равно минимальное и максимальное количества элементов в пирамиде вы- сотой й? 6.1.2 Покажите, что и-элементная пирамида имеет высоту (1б и!. 6.1.3 Покажите, что в любом поддереве невозрастаюшей пирамиды корень этого поддерева содержит наибольшее значение среди узлов поддерева. Где в невозрастаюшей пирамиде может находиться наименьший ее элемент, если все элементы различаются по величине? 6.1.5 Является ли массив с отсортированными элементами неубывающей пирамидой? 6.1.6 Является ли последовательность значений (23, 17, 14, б, 13, 10, 1, б, 7, 12) невозрастаюшей пирамидой? 6.1.7 Покажите, что если и-элементную пирамиду представить в виде массива, то ее листьями будут элементы с индексами ~и!2) + 1, (и/2) + 2,..., и.
6.2. Поддержка свойства пирамиды Для поддержки свойства невозрастающей пирамиды мы вызываем процедуру Млх-Ндлшру. Ее входными данными являются массив А и индекс г в этом массиве. При вызове процедуры Млх-Нплр1ру предполагается, что бинарные деревья с корнями 1.ирт(1) и К!опт(г) представляют собой невозрастаюшие пирамиды, но А[г) может быть меньше, чем значения в дочерних узлах (таким образом, нарушая свойство невозрастаюшей пирамиды). Процедура Млх-Ндлшру "сплавляет'* значение А~г] вниз по невозрастаюшей пирамиде, так, что поддерево с корневым элементом с индексом 1 подчиняется свойству невозрастаюшей пирамиды.
Глава б. Пирамидальная сортировка ].:)б 8, )9 )оу )'. т ".': (в) (б) '(бн 2 3 в,т ~в; (о(' ' (7~~ ~х,, (в) Рис. б 2. Работа процедуры Млх-Нялшгт(А,2), где А.леар-виве = 1О. (в) Исяспнвя конфигурация, в юторой значение А [2] в узле в = 2 нарушает свойство невозрвстающей пирамиды, посюльку оно меньше, чем кюкдое из дочерних значений.
Свойство невозрвствющей пирамиды восствнавлввве(ся для узла 2 в части (б) путем обмена А[2] с А[4], юторый при этом нарушает свойство невозрвстеюшей пирамиды для узла 4. В рекурсивном вызове Млх-Нялщгу(А, 4) значение в = 4. После обмена А]4] с А[9], квк показано в части (в), ситуация в узле 4 исправляется, и рекурсивный вызов Млх-Нялг)гу(А, 9) не вносит никаких изменений в полученную структуру данных. МЛХ-НЕЛР! Р з'(А, З) 1 1 = ЕЕРТ(з) 2 т = К)цнт(з) 3 ]з 1 < А.Беар-в(яе и А[1] > А[з] 4 (атуев! = 1 5 е)яе (атуев! = з' б ]з т < А.))еар-явке и А[т] > А[(отдел(] 7 1атуев! = т 8 И" (а(уев! ф з 9 Обменять А[з] и А[1атуев(] 10 Млх-Нелшру(А, 1атуев() На рис. 6.2 пок(мана работа процедуры Млх-Нелр(ру. На каждом шаге определяется больший нз элементов А[з], А[1.егт(з)] и А[Винт(з)], и его индекс сохраняется в переменной 1атуев!.
Если наибольшим оказывается А[з], то поддерево с корнем з уже представляет собой корректную невозраста(оиру(о пирамиду и процедура завершает работу. В противном случае наибольшим оказывается один из двух дочерних элементов, и процедура выполняет обмен А[з] с А[1а)уев(], что Уаств П. Сортировка а аорвдковав статистика приводит к тому, что для узла? и его дочерних узлов выполняется свойство невозрастающей пирамиды.
Однако теперь исходное значение А[1] оказывается в узле с индексом 1агдев1, так что поддерево с корнем 1агдев1 может нарушать свойство невозрастающей пирамиды. Следовательно, необходимо рекурсивно вызвать процедуру Млх-Нелигу уже для этого дерева. Для работы процедуры Млх-Нелг1гу на поддереве размером и с корнем в заданном узле 1 требуется время 9(1), необходимое для исправления отношений между элементами А[1], А[1.егт(1)] и А[Кинг(г)], плюс время работы этой процедуры с поддеревом, корень юторого находится в одном из дочерних узлов узла 1.
Размер каждого из таких дочерних поддеревьев не превышает величину 2п/3, причем наихудший случай осуществляется, югда последний уровень заполнен наполовину. Таким образом, время работы процедуры Млх-Нелигт описывается рекуррентным соотношением Т(п) ( Т(2п/3) + Н(1) . Решение этого рекуррентного соотношения, согласно случаю 2 основной теоремы (теорема 4.1), имеет вид Т(п) = 0(1к и). По-другому время работы процедуры Млх-Нелигу с узлом, который находится на высоте и, можно выразить как 0(Ь).
Упражнении 6.2.1 Воспользовавшись рис. 6.2 в качестве образца, проиллюсгрируйте работу процедуры Млх-Нелигу(А,З) с массивом А = (27,17,3,16,13,10,1,5,7,12,4,8,9,0). 6.2. 2 Используя в качестве отправной точки процедуру Млх-НелР1гу, напишите псевдокод процедуры М1н-Нели гу (А, 1), которая выполняет соответствующие действия над неубывающей пирамидой. Каково время работы процедуры МпчНелигт по сравнению со временем работы процедуры Млх-Нелигу? 62.З Как влияет на вызов процедуры Млх-Нелигт(А, г) ситуация, когда элемент А[1] больше, чем его дочерние элементы? 6.2.4 К чему приведет вызов процедуры Млх-Нелигу(А, г) в случае 1 > А.
леар-веке /2? 6.2.6 Код процедуры Млх-Нелг!гу достаточно рационален, если не считать рекурсивного вызова в строке 10, из-за которого некоторые компиляторы могут сгенерировать неэффективный код. Напишите эффективную процедуру Млх-Нелигу, в которой вместо рекурсивного вызова использовалась бы итеративная управляющая конструкция (цикл).
!85 Глава 6 !гира иидальаав сортировка 6.2. 6 Покажите, что в наихудшем случае время работы процедуры Млх-НЕлр1РУ на пирамиде размером п равно П(16 п). (Указание! в пирамиде с и узлами присвойте узлам такие значения, чтобы процедура Млх-Нелщру рекурсивно вызывалась в каждом узле, расположенном на простом пути от корня до листа.) 6.3.
Построение пирамиды Процедуру Млх-Нелшру можно использовать в восходящем направлении для того, чтобы преобразовать массив А[1 .. п[, где п = А. 1епд1!г, в невозрастающую пирамиду. В соответствии с упр. 6.1.7 элементы в подмассиве А[([п/2) + 1) .. п[ представляют собой листья дерева, поэтому каждый из них можно считать одно- элементной пирамидой, с которой можно начать процесс построения.
Процедура Вгггеп-Млх-НелР проходит по остальным узлам и для каждого из них выполняет процедуру Млх-Нелргру. В15!1л)-Млх-Нелр(А) 1 А.Ьеар-в(зе = А.1епдгЬ 2 1ог( = [А.1епд0г/2) йозгпсо 1 3 Млх-НелР1Ру(А,() На рис. 6.3 показан пример работы процедуры Вгггеп-Млх-Нелр. Чтобы показать корректность работы процедуры В151егз-Млх-Нелр, воспользуемся следующим инвариантом цикла. В начале каждой итерации цикла (ог в строках 2 и 3 каждый узел поде 1+ 1,1+ 2,..., п является корнем невозрастающей пирамиды.
Необходимо показать, что этот инвариант справедлив перед первой итерацией цикла, сохраняется при каждой итерации и позволяет продемонстрировать корректность алгоритма после его завершения. Инициализация. Перед первой итерацией цикла 1 = [п/23. Все узлы с индексами [п/2) + 1, [п/2) + 2,...,п являются листьями, поэтому каждый из них является корнем тривиальной невозрастающей пирамиды.
Сохранение. Чтобы убедиться, что каждая итерация сохраняет инвариант цикла, заметим, что узлы, дочерние по отношению к узлу 1, имеют номера, которые больше 1. В соответствии с инвариантом цикла оба эти узла являются корнями невозрастающих пирамид. Это именно то условие, которое требуется для вызова процедуры Млх-НелР1ру(А,(), чтобы преобразовать узел с индексом 1 в корень невозрастаюшей пирамиды. Кроме того, при вызове процедуры Млх-НелР1Ру сохраняется свойство пирамиды, заключающееся в том, что все узлы с индексами 1+ 1, 1+ 2,..., п являются корнями невозрастающих пирамид. Уменьшение индекса 1 в цикле 1ог обеспечивает выполнение инварианта цикла для следующей итерации.
1ВГ Глава д Пирамидакьнак сортировка Завершение. После завершения цикла 1 = О. В соответствии с инвариантом цикла все узлы с индексами 1, 2, ..., п являются корнями иевозрастающих пирамид. В частности, таким корнем является узел 1. Простую верхнюю оценку времени работы процедуры ВО1п>-Млх-НиАР можно получить следующим образом. Каждый вызов процедуры МАх-Нияг1гу имеет стоимость 0(18 и), а всего имеется 0(п) таких вызовов. Таким образом, время работы алгоритма равно 0(п 18 и).
Эта верхняя граница, будучи корректной, не является асимптотически точной. Чтобы получить более точную оценку, заметим, что время работы МяхНвлг1гу в том или ином узле зависит от высоты этого узла, и при этом большинспю узлов расположено на малой высоте. При более тщательном анализе принимается во внимание тот факт, что высота и-элементной пирамиды равна (18 и) (упр. 6.1.2) и что на любом уровие иа высоте й содержится ие более (п(2"+' ~ узлов (упр. 6.3.3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
