Лекции по информатике (984119), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

Итак, мы не только нашли минимальный элемент, но и сохранили иерархию субминимальпых (локально минимальных) элементов, теряемую при сортировке выборкой. Чтобы воспользоваться этой структурой, надо от победителя от»равиться к призерам, осуществив спуск вдоль пути, отмеченного наименьшим элементом. Все вершины его пути надо исключить из дерева, .заменив на, пустой элемент (квадратнук> дырку), Далее, поднимаясь назад по дыркам этого же пути, надо выполнить переигровку турнира для определения нового побечителя в отсутствие прежнего. При этом элемент, соревнук>щийся с пустым местом (+ со, поскольку пш>(а, ~ зс) = а), автоматически проходит в следук>щий тур.

В результате этого процесса в корень переместится паимепыпий из оставшихся элементов. Его также можно иск:почить из дерева, поместив в очередь отсортированных элементов. Повторяя этот процесс дс> полной выемки нспустых элементов из дерева, полу'шм отсортированную последовательность, Путь >юбедителя отмечен дырками Переигровка (дырка на листе победителя остается) Дадим сложностную оценку турнирной сортировки. 11а каждом из и шагов требуется только 11о8, п~ + 1 сравнений (высота дерева!). Таким образом, общее число сравнений составит и 1о8~ п. Оценим теперь стоимость построения дерева.

Сложность построения дерева оценивается в и шагов ~88~: для построения дерева из 127 элементов необходимо построить 32 дерева размером 3, 16 деревьев размером 7, 8 деревьев размером 15, 4 дерева размером 31, 2 дерева размером б3 и одно дерево размером 127. В худшем случае это требует 32 1+ 16 2+ 8 3+ 4 4+2 5+ 1 6 = 120 продвижений. Для и = 2" — 1 верхняя граница числа элементарных перемещений равна ,'~ 12" ' '=2ь — 6 — 1<и. 1<ч<п Это же доказательство справедливо и для и ф 2ь — 1. "1'аким образом, общая оценка пирамидальной остается линеарифмической, что является весьма существенным улучшением не толысо простых квадратичных методов, но и сублинейных (малополиномиальных) шелловских и' ' ~. Для практической реализации сортировки с помощью дерева выбора осталось лишь указать способ эффективного построения и использования этого дерева.

Если вспомнить сплошное поуровневое представление турнирного дерева, то возникает простой способ его размещения, правда., требующий двойного расхода памяти: сначала размещаются участники турнира, потом - победители пар, за ними - победители победителей и т. д.

Их число и+ в~2+и/4+... = 2п — 1. Если бы не двойной расход памяти, эта, простая и быстрая схема широко бы применялась. Победитель пары первого круга (и,, а... ~) находится по легко вычислимому адресу п + гЖч2. Чтобы заполнить второй уровень, необходимо запомнить индекс последнего записанного в первом круге элемента и, + идти 2 и т. д.

Для полного турнирного дерева без неявок и отказов (т. е. с 2~ участниками) заполнение дерева совсем тривиально: в качестве базового адреса для размещения уровня дерева необходимо выбирать 2ь ~ ~, где у' помер уровня. Итак, из-за дублирования в дереве выбора победивших элементов пространственная сложность алгоритма возрастает вдвое.

Для того чтобы сократить обьем памяти дерева выбора с 2"' ' элемента до и, необходимо применить пирамидальное улу пление традиционных древовидных сортировок. Пирамида определяется как последовательность ключей, 6ь, 6ь~~....., 6л, такая что 6, < 6~,, и 6,, < 6~;.ы для г = Л,..., Л/2. Пирамида отлича,ется от турнирного дерева отсутствием дубликатов элементов сортиру- емой последовательности.

Если любое двоичное дерево отображать в массив поуровневой схемой Г' Г~ /~ А Л А 68 69 610 611 612 613 614 615 то деревья сортировки становятся пирамидами, и в верхушку попадает наименьший элемент Ьч — — пшЦЬн 6~,..., 6„). Рассмотрим построение на базе некоторой пирамиды с заданными элементами 6 а~и..., Ьл для некоторых значений Л и Л расширенной пирамиды Ьь,..., Ьл с добавленным элементом х. Возьмем, например, пирамиду Ьн 6а,..., 6т 44 3 3 3 6~. и добавим к ней слева элемент 6~ = 44. Вносимое в пирамиду новое значение всегда ставится в се вершину и начинает играть в поддавки с примыкающими элементами, спускаясь вниз по направлению к наименьшему из двух подчиненных элементов, и пропуская наверх этот наименьший элемент.

Элементы с индексами г и у, где 1' = 21 или у = 21 1 1, так обмениваемые при перестроении дерева выбора, сохраняют неизменными условия пирамидальности. В нашем примере значение 44 сначала меняется местами с 06, затем с 12, и в результате образуется дерево Г' Б й4 18 О44 Сформулируем алгоритм вставки элемента в пирамиду. Как уже говорилось, первоначально элемент помещается в ес вершину, 1 = 1. Рассмотрим тройку элементов с индексами г, 2с, 2ю', ~ 1. Во-первых, по построению пирамиды, элементы 21 и 2ю' ~- 1 являются потомками г-того элемента. Выберем наименыпий из этих трех элементов.

Если оп находится на г-той позиции, то вставка элемента завершается. Иначе обозначим позицию наименьшего элемента буквой 1, где у' = 2~,' или у = 2? + 1. 1?оменяем местами элементы 1 и у, положим 1:= 1 и продолжим пропссс сравнений и обменов с 1-той позиции, куда в результате итерапии был помещен вставляемый элемент. 1?роцссс вставки в пирамиду можно проиллюстрировать на таком примере. Согласно известной шуткс, в каждой иерархии любой ее член занимает место согласно уровню своей компетс;нтности (некомпетентности). Новичок, .попадая в эту структуру, сначала примеряет к себе высшую должность, а потом постепенно спускается по иерархии вниз до тех пор, пока не будет руководить теми, кто компетентнее его.

Ввиду иерархичности структуры дерева выбора, скромный вариант (движение снизу вверх), в принципе возможен, но никогда не применяется, поскольку требует линейного, а не логарифмического времени. В 1963 году ?э. Флойдом был предложен лаконичный способ построения пирамиды на месте. Верхняя половина 6 ...6, организуемого в пирамиду массива Ьс...6„, где ии = (ис??ч2) + 1 становится нижним уровнем двоичного дерева выбора. Далее, в оставшейся части массива надо построить вышес;тсящие уровни дерева на основе отношения порядка: элементы с индексами 6, .2А', 26+ 1 упорядочиваются так, чтобы больший из них находился в 1с-ой ячейке массива. Пирамида постепенно расширяется влево путем добав- ления новых элементов, переставляемых на, легко вычислимую надлежащую позицию. Процесс формирования пирамиды из и элементов 6,... 6„на месте описывается так: 1..: — (и с??ъ 2) + 1; жЫ?е ?.

> 1 с?о Ьеи?п ?.: 1 — 1: я?1 (?., п1; епс1; В этом коде Е присваивается значение ис??ч2 + 1, шэскольку все элементы с большими индексами лежат в нижнем слое пирамиды и не имеют потомков. В первой итерации алгоритм упорядочивает микропирамиду, состоящую из Е-того, 2Е-того и 2Е + 1-ого элементов. Этот процесс продолжается до исчерпания таких пирамид. В результате первой итерации получим и/4 трехэлементных двухэтажных пирамид. В резульгате дальнейшей деятельности возникнут семиэлемсптные трехэтажные пирамиды (семирамис?ьсс ), в которых произойдут, если необходимо, одно- и двузвенные цепочки обменов. После обработки и/8 пирамид из 7 элементов, будут получены пирамиды из 15, 31 и т. д, Этот процесс завершится, поскольку в массиве содержится конечное число элементов.

Кроме того, этот алгоритм действительно строит пирамиду: в силу описанного алгоритма вставки в пирамиду и того факта, что один элемент тоже является пирамидой, по индукции следует, что описанная трехэлементная конструквия также является пирамидой. Индукпия осуществляется по высоте пирамиды: при помощи вышеописанного алгоритма, вставки из одного элемента и двух пирамид высоты ?с (каждая из которых содержит не более 2 — 1 элементов, поскольку некоторые из пирамид могут быть неполными!) можно создать пирамиду высоты ?с 1 1 (которая содержит не более 2" " — 1 элементов).

Процесс построения пирамиды описанным алгоритмом выглядит так (черта отделяет пирамидальную часть массива и еще неооработанные элементы:, пирамидальная структура расположена справа от черты): 12 42 ~ 94 18 06 67 12 ~42 94 18 06 67 ! 06 42 94 18 12 67 06 55 94 18 12 67 12 55 94 !8 44 67 44 55 44 55 14 55 44 ~ 42 06 42 Чтобы приспособить эту пирамиду лля целей сортировки, необходимо проделать и шагов выталкивания наверх наименьшего элемента, и направить полученные элементы в некую выходную очередь.

Однако, поскольку при всяком выталкивании число элементов в пирамиде уменьшается на 1, то можно организовать эту очередь в том же массиве, просто поменяв местами первый и последний элементы, и повторить процесс вставки новой вершины в пирамиду, основанную на массиве длины и — 1 (в этом и состоит идея Флойда, предложившего минимальную по памяти турнирную сортировку). В результате наверх придет второй по величине элемент.

Его следует поменять с элементом на позиции и — 1 и осуществить спуск нового элемента в пирамиде из и, — 2 элементов и т. д. Алгоритм сортировки готовой пирамиды выглядит так: Примененный к готовой пирамиде алгоритм сортировки работает так: Поскольку этот алгоритм на последни>ю позицию помещает минимальный элемент, на предпоследнюю второй по величине и т. д., а на первой позиции оказывается максимальный из элементов, то элементы оказываются упорядоченными по убыванинх Этот недостаток легко исправить, поменяв отношение порядка в процедуре в1Я) на противоположное. «Правильная» функция Неарвогф выглядит так: ргосес1пге НеарЯог1(айаг а: эес1): 1' Соргаировка НеарБог1 — иросвиваииелс ~1 айаг 1е К: 1пс1ех; х: йеш; К:=- и: тс Ы1е К = 1 с1о Ьеи1н х :-- а [ Ц; а~Ц: аЩ; а(Щ:-- х; Кг- К вЂ” 1; э1й (1, К); епс4; 06 42 12 12 42 18 18 42 44 42 55 44 44 55 94 55 67 94 67 94 ~ 55 94 ~ 67 55 55 94 18 55 94 67 55 94 67 67 94 ~ 18 67 ~ 42 18 ! 44 42 18 44 42 18 44 67 44 ( 06 ( 12 06 12 06 12 06 12 06 12 06 12 06 ргосес1нге Влй[Ь,.

К: шс1ех):, айаг 1, ) : 1ис1ех; Х,2: ЫЕШ; Ьеи1п : — 1.; 2 * 1.; х: а[1); 11' ц < К) апс1 [аЦ .= а[) ' 1)) СЬеп э: 3 - 1; жЬ11е [) < — К) апс1 [х < аЦ) с1о Ьеиш 2: — а[1); а [ 1 ) : -- а [1 ); а[э):-- 2; . 3' ):-=-2* 1; 11 Ц < К) апс1 [а[1) < а[1 + Ц) ФЬеп 3 ь- 3 епс1; епс1:, (О1Я Ьедш (ЛеарЯОГ13 1,: — [и с11у 2) + 1: Мп1е 1 > 1 с1о Ьеиш Ь:=- 1. — 1; алй, [Ь, и); епс1; К: — и; жЬ11е К, ) 1 с1о Ьеиш х . 11[1) а[1) г а[К); а)К): - х; К; — К вЂ” 1; элй [1., К):, епс1; епс1; (Неар8огЦ Проанализируем пирамидальную сортировку.

Характеристики

Список файлов лекций