Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 36
Текст из файла (страница 36)
Рассматривая пирамиду как дерево, определим высоту ее узла как число ребер в самом длинном простом нисходящем пути от этого узла к какому-то из листьев дерева. Высота пирамиды определяется как высота его корня. Поскольку и-элементная пирамида строится по принципу полного бинарного дерева, то ее Глава б. Пирамидальная сортировка 181 высота равна 6 (18п) (см. упражнение 6.1-2).
Мы сможем убедиться, что время выполнения основных операций в пирамиде приблизительно пропорционально высоте дерева, и, таким образом, эти операции требуют для работы время О (18 п). В остальных разделах этой главы представлены несколько базовых процедур и продемонстрировано их использование в алгоритме сортировки н в структуре данных очереди с приоритетами. ° Процедура МАх НЕАк1гу выполняется в течение времени О (18 и) и служит для поддержки свойства невозрастания пирамиды.
° Время выполнения процедуры Во1ьо МАх НнАР увеличивается с ростом количества элементов линейно. Эта процедура предназначена для создания невозрастающей пирамиды из неупорядоченного входного массива. ° Процедура Ннлкзокт выполняется в течение времени О (и 18 и) и сортирует массив без привлечения дополнительной памяти. ° Процедуры МАх НпАк 1мзнкт, НнАк Ехтклст Млх, НнАР 1мсккАзн Кеу и Ннлк МАх~мим выполняются в течение времени О (18п) и позволяют использовать пирамиду в качестве очереди с приоритетами. УПРажНЕНИЯ 6.1-1. Чему равно минимальное и максимальное количество элементов в пирамиде высотой Й? 6.1-2.
Покажите, что и-элементная пирамида имеет высоту 118 п1. 6.1-3. Покажите, что в любом поддереве невозрастающей пирамиды значение корня этого поддерева не превышает значений, содержащихся в других его узлах. 6.1-4. Где в невозрастающей пирамиде может находиться наименьший ее элемент, если все элементы различаются по величине? 6.1-5. Является ли массив с отсортированными элементами неубывающей пирамидой? 6.1-6.
Является ли последовательность (23, 17, 14, б, 13, 10, 1, 5, 7, 12) невозрастающей пирамидой? 6.1-7. Покажите, что если и-элементную пирамиду представить в виде массива, то ее листьями будут элементы с индексами ~ п7* 21 + 1, 1п/21 + 2,..., п. 182 Часть 11.
Сортировка и порядковая статистика 6.2 Поддержка свойства пирамиды Процедура Млх Нелиеу является важной подпрограммой, предназначенной для работы с элементами невозрастающих пирамид. На ее вход подается массив А и индекс 1 этого массива. При вызове процедуры Млх НЕлиРУ предполагается, что бинарные деревья, корнями которых являются элементы 1.еет(1) и К10нт(г), являются невозрастающими пирамидами, но сам элемент А [1] может быль меньше своих дочерних элементов, нарушая тем самым свойство невозрастающей пирамиды. Функция Млх НелР!еу опускает значение элемента А [1] вниз по пирамиде до тех пор, пока поддерево с корнем, отвечающем индексу г, не становится невозрастающей пирамидой: Млх Нелиеу(А,Е) 1 1 - 1.ест(1) 2 т дронт(1) 3 111 < Беар з1зе[А] и А[1] > А[1] 4 1Ьеп 1атдеаг — 1 5 е1зе 1атдеа1 6 й1т ( Беар авве[А] и АЯ > А[1атдеа1] 7 11зеп 1атдеа1 — т 8 11 1атдеа1 ф г' 9 гпеп Обменять А[1] + А[1атдеа1] 10 МЛХ НЕЛИЕу(А, 1атдеа1) Действие процедуры Млх НЕлигу проиллюстрировано на рис.
6.2. На каждом этапе ее работы определяется, какой из элементов — А [1], А [Ьег1(1)] илн А [Вьда1 (1)] — является максимальным, и его индекс присваивается переменной 1атдез1. Если наибольший элемент — А [1], то поддерево, корень которого находится в узле с индексом г', — невозрастающая пирамида, и процедура завершает свою работу. В противном случае максимальное значение имеет один из дочерних элементов, и элемент А [1] меняется местами с элементом А [1атдеа1].
После этого узел с индексом г' и его дочерние узлы станут удовлетворять свойству невозрастаюшей пирамиды. Однако теперь исходное значение элемента А [1] присвоено элементу с индексом 1атдеа1, и свойство невозрастающей пирамиды может нарушиться в поддереве с этим корнем. Для устранения нарушения для этого дерева необходимо рекурсивно вызвать процедуру Млх Нелиеу.
На рис. 6.2 показана работа процедуры Млх Нелиеу(А, 2). В части а этого рисунка показана начальная конфигурация, в которой элемент А [2] нарушает свойство невозрастающей пирамиды, поскольку он меньше, чем оба дочерних узла. Поменяв местами элементы А [2] и А [4], мы восстанавливаем это свойство в узле 2, но нарушаем его в узле 4 (часть б рисунка). Теперь в рекурсивном вызове процедуры Млх Нелигу(А, 4) в качестве параметра выступает значение Глава 6.
Пирамидальная сортировка 183 ! . 'в', ! , !6 ! ву '(в в! ! '!е! !3,, ' в! Рис. 6.2. Работа процедуры Млх Нллшгу(А, 2) при Ьеар вие [А] = 10 Т(тв) < Т(2тв/3) + 0 (1). Решение этого рекуррентного соотношения, в соответствии со вторым случаем основной теоремы (теоремы 4.1), равно Т(п) = О (18п). По-другому время ра- боты процедуры Млх Нелг!Ру с узлом, который находится на высоте Ь, можно выразить как О (Ь). в = 4. После перестановки элементов А [4] и А [9] (часть в рисунка) ситуация в узле 4 исправляется, а рекурсивный вызов процедуры Млх Ннлг!Ру(А,9) не вносит никаких изменений в рассматриваемую структуру данных.
Время работы процедуры Млх Ннлшгу на поддереве размера и с корнем в заданном узле в вычисляется как время 6 (1), необходимое для исправления отношений между элементами А [в], А [Беат (в)] или А [ВвдМ (в)], плюс время работы этой процедуры с поддеревом, корень которого находится в одном из дочерних узлов узла в. Размер каждого из таких дочерних поддеревьев не превышает величину 2тв/3, причем наихудший случай — это когда последний уровень заполнен наполовину. Таким образом, время работы процедуры Млх Нелшгу описывается следующим рекуррентным соотношением: 184 Часть Н. Сортировка и порядковая статистика Упражнения 6.2-1.
Используя в качестве модели рис. 6.2, проиллюстрируйте работу процедуры Млх НелР1Ру(А,З) с массивом А = (27,17,3,16,13,10,1,6,7,12, 4,8,9,0). 6.2-2. Используя в качестве отправной точки процедуру Млх НелР1Рт, составьте псевдокод процедуры Мпч НелР1Ру(А,1), выполняющей соответствующие действия в неубывающей пирамиде.
Сравните время работы этих двух процедур. 6.2-3. Как работает процедура Млх НелР1Ру(А, г) в случае, когда элемент А [г] больше своих дочерних элементов? 6.2-4. К чему приведет вызов процедуры Млх НелР1Ру(А,1) прн 1 > > аеар зззе [А]/2? 6.2-5. Код процедуры Млх НЕлшРу достаточно рационален, если не считать рекурсивного вызова в строке 10, из-за которого некоторые компиляторы могут сгенерировать неэффективный код. Напишите эффективную процедуру Млх Нелшгу, в которой вместо рекурсивного вызова использовалась бы итеративная управляющая конструкция (цикл). 6.2-6. Покажите, что в наихудшем случае время работы процедуры Млх НелР1Гу на пирамиде размера и равно П (18 п). (Указание: в пирамиде с и узлами присвойте узлам такие значения, чтобы процедура Млх НелР1Ру рекурсивно вызывалась в каждом узле, расположенном на пути от корня до одного из листьев.) 6.3 Создание пирамиды С помощью процедуры Млх Нелв1Ру можно преобразовать массив А [1..п], где и = 1епдй [А], в невозрастающую пирамиду в направлении снизу вверх.
Из упражнения 6.1-7 известно, что все элементы подмассива А [(~ и/2] + 1) ..и] являются листьями дерева, поэтому каждый из них можно считать одноэлементной пирамидой, с которой можно начать процесс построения. Процедура Впп.п Млх НелР проходит по остальным узлам и для каждого из них выполняет процедуру Млх НелР1Ру: В1льп Млх НелР(А) 1 Беар яме[А] — 1епд1а[А] 2 1ог 1 — [1епдй[А]/2] йоттп1о 1 3 до МЛХ НЕЛР1Ру(А, г) Пример работы процедуры В01ь1э Млх НелР показан на рис. 6.3. В части а этого рисунка изображен 10-элементный входной массив А и представляющее Глава б.
Пирамидальная сортировка 185 7 3 Ы, , ~~3 !74! !3~ ~ 7 ! 0! 7 Я г! ! !!4 7 0)7 (7) Рис. 6.3. Схема работы процедуры Вшпп МАх Нелг его бинарное дерево. Из этого рисунка видно, что перед вызовом процедуры МАх НеАР4Ру(А,г) индекс цикла 1 указывает на 5-й узел. Получившаяся в результате структура данных показана в части б. В следующей итерации индекс цикла 1 указывает на узел 4. Последующие итерации цикла 1ог в процедуре Вп4ьп МАх НеАР показаны в частях в-д рисунка. Обратите внимание, что при вызове процедуры МАх НеАР4Ру для любого узла поддеревья с корнями в его дочерних узлах являются невозрастающими пирамидами. В части е показана невозрастающая пирамида, полученная в результате работы процедуры Вг77п> МАх НеАР. 186 Часть 1!.
Сортировка и порядковая статистика Чтобы показать, что процедура Вин.о МАх НЕАР работает корректно, воспользуемся сформулированным ниже инвариантом цикла. Перед каждой итерацией цикла Гог в строках 2-3 процедуры Ви~ьп МАх НеАР все узлы с индексами з'+ 1, г+ 2,..., п являются корнями невозрастающих пирамид. Необходимо показать, что этот инвариант справедлив перед первой итерацией цикла, что он сохраняется при каждой итерации, и что он позволяет продемонстрировать корректность алгоритма после его завершения.
Инициализация. Перед первой итерацией цикла 1 = '1п/21. Все узлы с индексами 1п/2~ + 1, (и/2) + 2,..., п — листья, поэтому каждый из них является корнем тривиальной невозрастающей пирамиды. Сохранение. Чтобы убедиться„что каждая итерация сохраняет инвариант цикла, заметим, что дочерние по отношению к узлу з' имеют номера, которые больше г. В соответствии с инвариантом цикла, оба эти узла являются корнями невозрастающих пирамид.
Это именно то условие, которое требуется для вызова процедуры МАх НеАлгу(А, г), чтобы преобразовать узел с индексом г в корень невозрастающей пирамиды. Кроме того, при вызове процедуры МАх НеАигу сохраняется свойство пирамиды, заключающееся в том, что все узлы с индексами г+ 1, г + 2,..., п являются корнями невозрастающих пирамид. Уменьшение индекса г в цикле Гог обеспечивает выполнение инварианта цикла для следующей итерации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
