Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 41
Текст из файла (страница 41)
Для удобства будем рассматривать здесь лишь случай "наибольший из включенных первым исключается".) Вообще, если требуется исключить наибольший элемент, а затем вставить новый элемент я, можно выполнить процедуру "протаскивания" при 1 = 1, г = У и К = я. Если же необходимо вставить элемент без предварительного исключения, можно воспользоваться "восходящей" процедурой из упр.
16. (9) (10) () КЕТ(Р) > КЕТ(1.ЕРТ(Р)), КЕТ(Р) > КЕУ(НХСНТ(Р)); 01БТ(Р) = 1 + !п(91БТ((.ЕРТ(Р)),01ЯТ(НТСНТ(Р))); 91ЯТ(КЕРТ(Р)) > 01БТ(Н10НТ(Р)), Соотношение (9) аналогично условию существования пирамиды (3) и служит гарантией того„что в корне дерева находится наибольший ключ, а соотношение (10)— зто просто определение поля 91БТ, сформулированное выше. Соотношение (11) представляет собой интересное новшество: из него следует, что кратчайший путь к конечному узлу всегда можно получить, двигаясь вправо. Будем называть бинарное дерево с этим свойством левоеяюроняом деревом, поскольку оно, как правило, сильно "тянется" влево, Из этих определений ясно, что равенство 01БТ(Р) = и подразумевает существование, по крайней мере, 2" пустых поддеревьев, расположенных ниже Р; в противном случае нашелся бы более короткий путь от Р до концевого узла Л.
Таким образом, если в левостороннем дереве имеется Х узлов, то путь, ведущий нз корня вниз по направлению вправо, содержит н» более чем (1Я(Х + 1)) узлов. Новый Связанное представление приоритетных очередей. Эффективный способ представления приоритетных очередей в виде связанных бинарных деревьев предложил в 1971 году Кларк Э. Крэйн (см.
С1аг1г А, Сгапе, ТесЬшса) Верогг БТАЕь СЯ-72-259 (Сошрпгег Яс!енсе 1)ераггшепс, Ягап(огб Ншгегагу, 1972))). Его метод требует наличия в каждой записи двух полей связи и короткого поля счетчика, но по сравнению с пирамидами он обладает следующими преимуществами.
!) Если с приоритетной очередью работают, как со стеком, то операции включения и исключения более эффективны (они отнимают фиксированное время, не зависящее от длины очереди). Н) Записи никогда не перемещаются, изменяются только указатели. !Н) Можно слить две непересекаюпшеся приоритетные очереди, содержащие в общей сложности Ю элементов, всего за О(!оКХ) шагов. Немного видоизмененный метод Крейна проиллюстрирован на рис. 27, на котором показан особый тип структуры бинарного дерева. В каждом узле содержатся поле КЕУ, поле 91БТ и два поли связи — !.ЕРТ и Н10НТ.
Поле Р1БТ всегда устанавливается равным длине кратчайшего пути от этого узла до конечного узла (т. е. до пустого узла Л дерева). Если считать, что 91ЯТ(Л) = 0 и КЕг'(Л) = -оо, то поля КЕТ и 01БТ в этом дереве удовлетворяют слелующям соотношениям: Рнс. 2Т. Приоритетная очередь, представленная в виде левостороннего дерева. узел можно вставить в приоритетную очередь, пройдя по этому пути (см. упр. 33). Следовательно, в худшем стучае необходимо всего 0(1об)т') шагов. Наилучший случай достигается, когда дерево линейно (все связи Н10НТ равны Л), а наихудший случай — когда оно абсолютно сбалансировано. Чтобы удалить узел из корня, нужно просто слить два его полдерева. Операция слияния двух непересекающихся левосторонних деревьев, на которые ссылаются указатели Р н Ц, по своей цдее простец если КЕТ(Р) > КЕТ(Я), то берем в качестве корня Р н сливаем Ц с правым поддеревом Р. При этом изменится Р1ЯТ(Р), а ьЕГТ(Р) поменяется местами с Н1ьНТ(Р) в случае необходимости.
Нетрудно составить подробное описание этого щюцесса (см. упр. 33). Сравнение методов работы с приоритетными очередями. Если число узлов Х малб, то для поддержании приоритетной очереди лучше всего прибегнуть к одному из простых методов с использованием линейных списков. Если же тт' велико, то, очевидна, гораздо более быстрым будет метод, использующий пирамиду нли левостороннее дерево, время работы которого составляет порядка!ой)т. В разделе 6.2.3 будет рассмотрен еще один способ представления линейных списков— в виде сбалансирвваннмя деревьев. Он приводит нас к третьему методу, пригодному для представления приоритетных очередей со временем работы порядка (оба.
Поэтому уместно сравнить три данных метода. Иы видели, что операции нвд левосторониими деревьями, в целом, выполняются несколько быстрее, чем операции над пирамидамн, но пирамиды занимают меньше памяти. Сбалансированные деревья занимают примерно столько же памяти, сколько левосторонние (быть может, чуть меньше); операции над ними выполняются медленнее, чем над пирамидами, и программирование сложнее, но структура сбалансированных деревьев в некоторых отншпениях существенно более гибкая. Работая с пирамидами, не так просто предсказать, что произойдет с элементами, если у иих равные ключи. Нельзя гарантировать, что элементы с равными ключами будут обрабатываться по принципу "по|п|едним пришел — первым вышел" или "первым пришел — первым вьппел", если только ключ ие расширен и не содержит дополнительного поля "порядковый номер вставки"; тогда равных ключей просто нет. С другой стороны, если применять сбалансированные деревья, можно легко отоварить жесткие условия, относящиеся к равным ключам.
Можно также выполнять такие действия, как "вставить х непосредственно перед (или после) у". Сбалансированные деревья симметричны, так что в любой момент можно исключить либо наиболыпий, либо наименьший элемент, в то время как левосторониие деревья и пирамиды должны быть так или иначе ориентированы. (См., тем ие менее, упр. 31, в котором показано, как строить спымс|прпчнме пирамиды.) Сбалансированные деревья можно использовать и для поиска, и для сортировки. Из сбалансированного дерева можно довольно быстро удалять последовательные блоки элементов. Но два сбалансированных дерева нельзя слить менее чем за й(Х) и|ахов, в то время как два левосторонних дерева можно слить всего за О(!о8 Ю) шагов.
Итак, сортировка с использованием пирамид наиболее экономна с точки зрения требований к объему памяти; левосторонние деревья хороши тем, что позволяют быстро слить две иепересекаккциеся приоритетные очереди; и, если нужно, по весьма умеренной цене можно получить гибкость, предоставляемую сбалансированными деревьями. Ф. Со времени выхода в свет "пионерской" работы Уильямса н Крейна разработано много новых способов представления приоритетных очередей, Теперь в распоряжении програмлшстов имеется большое разнообразие опций, помимо простых списков, левостороннпх и сбалансированных деревьев. Некоторые ||з яих перечислены ниже: ° спрямлеииые деревья, которые обеспечивают обработку симметричной приоритетной очерю|и всего за 0(!о8 !ой М) п|агов, если все ключи лежат в заданном диапазоне 0 < К < М [Р.
чап Еш|!е Воаэ, В. Кааэ, Е. Х!)!эгга, Маг!|. Яуэгешэ Т!|соту 10 (1977), 99 — 127]; ° биномиальные очереди [Л. Ъ'и!1!еш!и, САСМ 12 (1978), 309-315; М, В. Вго|гп, ВТСОМР 7 (1978), 298-319]; ° пагоды [Л. Ггапсоп, О. Ъ'!епаог, Л. Уц!!1еп|!и, ГОСЯ 19 (1978), 1-7]; ь парные пирамиды [М. 1..
Ггебшап, В. Яеббетг!с!|, В. В. 8!еагог, К. Е. Таг)ап, А!8опс!ип!са 1 (1986), П1-129;,1. Т. 8|вако, Л. 8. Ъ'!г|ег, САСМ 30 (1987), 234-249]; в спиральные пирамиды [11. 11. Я!еа|ог, В. Е. Тат)ап, $1СОМР 15 (1986), 52-59]; ° пирамиды Фибоиаччи [М. 1».
Гге|Ьпап, В. Е. Тат)ап, УАСМ 34 (1987), 596-615] и более общие АГ-пирамиды [М. Е. Гге|!пшп, В. Е. 1т'Шаг|(, Х Сошрпгег ап|! Яуэгеш Ясй 48 (1994), 533-551]; ь календарные очереди [В. Вгохчп, САСМ 31 (1988), 1220-1227; О. А. Пах!эоп, САСМ 32 (1989), 1241-1243]; ° ослабленные пирамиды [3. К. ОНэсоБ, Н. Х. Оа)ке, К. БЬгсйгшап, К. Е. Таг1ап, САСМ 31 (1986), 1343-1354); ° острбга (М. 3. Р1эсЬег, М.
8. Рагегэоп,,)АСМ 41 (1994), 3-30]; ° "горячие" очереди (В. Ъ'. СЬегйаээйу, А. Ъ'. СоЫЬег8, С. 811чегэсе1п, ЗОВА 6 (1997), 83-92). Не все нз этих методов выдержали испытание временем. Лелостороннне деревья сеггэтня — уже анахронизм; ояи используются разве что в тех приложениях, в которых необхсдимо жестко соблюдать лэюцлплину "последним пришел — первым вышел", Детали реализации бнномлальиых очередей и пирамид Фпбоначчл можно найти в работе 11. Е.
Кпий, ТЬе 81апЕогс( СгарЬВаэе (Феи Уог)г: АСМ Ргеээ, 1994), 475-489. *Анализ пирамидальной сортировки. Алгоритм Н до сих пор не был полностью проанализирован математическими методами, но некоторые его свойства можно вывести без особого труда. Поэтому даяный раздел завершается довольно подробным анализом пирамид. На рис. 28 показана форма пирамиды из 26 элементов; каждый узел помечен двоичным числом, соответствующим его индексу в пирамиде. Звездочками на этой диаграмме помечены так называемые особмс уэлм, которые лежат на пути от 1 к Х Одна из наиболее важных характеристик пирамиды — множество размеров ее поддеревьев.
Например, на рис, 28 размеры поддеревьев с корнями в узлах 1, 2,..., 26 равны соответственно 26',15,10',7,7,6',3,3,3,3,3,3,2",1,1,1,1,1,1,1,1,1,1,1,1,1'. (12) Звездочками помечены особые поддеревьл с корнями в особых узлах; в упр. 20 показано, что если Л имеет двоичное представление (13) Х = (5„5„1 ... 515э)э, и = (!8Ю), то размеры особых подлеревьев равны (15л-1 ° ° ° 5150)2. (15а-т 5150)2, ° . ~(15150)2~ (150)э~ (Цэ (14) Неособые полдеревья всегда абсолютно сбалансированы, так что их размеры имеют вид 2 — 1. В упр. 21 показано, что среди неособых поддеревьев существует ровно Х вЂ” 1! ~ М -2 ~ 1Ф вЂ” 4! — ~ размером 1, ~ — ~ размером 3, ~ — ~ размером 7, ..., 2и-1 ~ (2" — 1) размера.
(15) Например, на рис. 28 изображено двенадцать неособых поддеревьев размером 1, шесть поддеревьев размером 3, два — размером 7 и одно — размером 15. Пусть э~ — размер полдерева с корнем 1, а Ми — мультимножество (эм эз,..., э,ч) всех этих размеров. Используя (14) и (15), легко вычислить Ми при любом заданном Х. В упр. 5.1,4-20 показано, что общее число способов построения пирамиды нз целых чисел (1,2,...,7ч') равно (16) Рнс.
28, Так выглядит пирамида из 26 = (11010)э элементов. Например, количество способов такого расположения 26 букв (А,В,С,..., Я) на рнс. 28„чтобы по вертикали сохранялся алфавитный порядок, составляет 26~Д26 10 6 2 1 1~з Зв 7з 15 Теперь можно проанализировать фазу построения пирамиды в алгоритме Н, т. е. вычислительные операции, которые завершаются до того, как иа шаге Н2 впервые выполнится условие 1 = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
