Алгоритмы - построение и анализ (1021735), страница 35
Текст из файла (страница 35)
Эта процедура предназначена для создания невозрастающей пирамиды из неупорядоченного входного массива. ° Процедура Ннлкзокт выполняется в течение времени О (и 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] 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.2. Работа процедуры Млх Нллшгу(А, 2) при Ьеар вие [А] = 10 в = 4. После перестановки элементов А [4] и А [9] (часть в рисунка) ситуация в узле 4 исправляется, а рекурсивный вызов процедуры Млх Ннлг!Ру(А,9) не вносит никаких изменений в рассматриваемую структуру данных. Время работы процедуры Млх Ннлшгу на поддереве размера и с корнем в заданном узле в вычисляется как время 6 (1), необходимое для исправления отношений между элементами А [в], А [Беат (в)] или А [ВвдМ (в)], плюс время работы этой процедуры с поддеревом, корень которого находится в одном из дочерних узлов узла в. Размер каждого из таких дочерних поддеревьев не превышает величину 2тв/3, причем наихудший случай — это когда последний уровень заполнен наполовину.
Таким образом, время работы процедуры Млх Нелшгу описывается следующим рекуррентным соотношением: Т(тв) < Т(2тв/3) + 0 (1). Решение этого рекуррентного соотношения, в соответствии со вторым случаем основной теоремы (теоремы 4.1), равно Т(п) = О (18п). По-другому время ра- боты процедуры Млх Нелг!Ру с узлом, который находится на высоте Ь, можно выразить как О (Ь).
! , !6 ! ву '(в ! '!е! ~".";~,.'~~ ( ! ) в! ! . 'в', ' ~)::;" 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 !!9! ! 3~ ~7 ) 0! 7 Я г! ! 9 !О Рис.
6.3. Схема работы процедуры Вшпп МАх Нелг его бинарное дерево. Из этого рисунка видно, что перед вызовом процедуры МАх НеАР7Ру(А,г) индекс цикла 1 указывает на 5-й узел. Получившаяся в результате структура данных показана в части б. В следующей итерации индекс цикла 1 указывает на узел 4. Последующие итерации цикла 1ог в процедуре Вп7ьп МАх НеАР показаны в частях в-д рисунка. Обратите внимание, что при вызове процедуры МАх НеАР!Ру для любого узла поддеревья с корнями в его дочерних узлах являются невозрастающими пирамидами. В части е показана невозрастающая пирамида, полученная в результате работы процедуры Вг7!п> МАх НеАР.
186 Часть 1!. Сортировка и порядковая статистика Чтобы показать, что процедура Вин.о МАх НЕАР работает корректно, воспользуемся сформулированным ниже инвариантом цикла. Перед каждой итерацией цикла Гог в строках 2-3 процедуры Ви~ьп МАх НеАР все узлы с индексами з'+ 1, г+ 2,..., п являются корнями невозрастающих пирамид. Необходимо показать, что этот инвариант справедлив перед первой итерацией цикла, что он сохраняется при каждой итерации, и что он позволяет продемонстрировать корректность алгоритма после его завершения. Инициализация.
Перед первой итерацией цикла 1 = '1п/21. Все узлы с индексами 1п/2~ + 1, (и/2) + 2,..., п — листья, поэтому каждый из них является корнем тривиальной невозрастающей пирамиды. Сохранение. Чтобы убедиться„что каждая итерация сохраняет инвариант цикла, заметим, что дочерние по отношению к узлу з' имеют номера, которые больше г. В соответствии с инвариантом цикла, оба эти узла являются корнями невозрастающих пирамид.
Это именно то условие, которое требуется для вызова процедуры МАх НеАлгу(А, г), чтобы преобразовать узел с индексом г в корень невозрастающей пирамиды. Кроме того, при вызове процедуры МАх НеАигу сохраняется свойство пирамиды, заключающееся в том, что все узлы с индексами г+ 1, г + 2,..., п являются корнями невозрастающих пирамид. Уменьшение индекса г в цикле 1ог обеспечивает выполнение инварианта цикла для следующей итерации. Завершение. После завершения цикла г = О. В соответствии с инвариантом цикла, все узлы с индексами 1, 2,..., п являются корнями невозрастающих пирамид. В частности, таким корнем является узел 1.
Простую верхнюю оценку времени работы процедуры Вшпп МАх НеАР можно получить следующим простым способом. Каждый вызов процедуры МАх НеАйгу занимает время О (18п), и всего имеется О (и) таких вызовов. Таким образом, время работы алгоритма равно О (п!бп). Эта верхняя граница вполне корректна, однако не является асимптотически точной. Чтобы получить более точную оценку, заметим, что время работы МАх Нелигу в том или ином узле зависит от высоты этого узла, и при этом большинство узлов расположено на малой высоте.
Прн более тщательном анализе принимается во внимание тот факт, что высота п-элементной пирамиды равна (18п) (упражнение 6.1-2) и что на любом уровне, находящемся на высоте й, содержится не более ~п/2ь+~~ узлов (упражнение 6.3-3). Время работы процедуры МАх Нелигу при ее вызове для работы с узлом, который находится на высоте Ь, равно О (л), поэтому верхнюю оценку полного времени работы процедуры Впп.п МАХ НЕАР можно записать следующим Глава 6. Пирамидальная сортировка 187 образом: Ря ь) Рв п) Е [' —,"„,1О(8)=О пŠ— ", а=а л=о Сумму в последнем выражении можно оценить, подставив з = 1/2 в формулу (А.8), в результате чего получим: 6 1/2 = 2. ( - /2)' Таким образом, время работы процедуры Вгльп Млх Нилг можно ограничить следующим образом: О п ~~> — „=О п~ — „=О(п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
