Главная » Java, Структуры данных и алгоритмы » Восходящее построение пирамиды

0

Анализ алгоритма сортировки пирамиды показывает, что можно создать пирамиду для сортировки п пар «ключ-элемент» за 0(п log п) времени, выполняя п раз операцию insertltem, и затем использовать эту пирамиду для извлечения элементов в нужном порядке. Тем не менее в случае если заранее имеются все ключи, возможен альтернативный восходящий (bottom-up) метод построения, выполняющийся за О(п) времени.

В этом разделе описывается упомянутый метод, который может быть включен в класс Heap в качестве конструктора вместо заполнения пирамиды серией операций insertltem. Для простоты исследований опишем восходящее построение пирамиды, исходя из условия, что количество ключей п представлено целым числом:

n = 2h -1.

Поскольку пирамида — это полное бинарное дерево с укомплектованными уровнями, то она имеет высоту h = log(п + 1).

При нерекурсивном просмотре восходящее построение состоит из h = log(rt + 1) стадий.

Рис. 7.8. Три начальных шага первой стадии внутренней сортировки. Пирамидальная часть вектора выделена штриховой линией. Рядом с вектором изображено бинарное дерево пирамиды, хотя оно и не создается этим алгоритмом

[1]   На первой стадии (рис. 7.9, а) создается (п + \)/2 простых пирамид, каждая из которых сортирует один ключ.

[1]   На второй стадии (рис. 7.9, b-с) соединяются пары простых пирамид и, добавляя новый ключ, формируется (п + 1)/4 пирамид, каждая из которых сортирует три ключа. Новый ключ располагается в корне и может заменяться ключом, хранящимся в’дочернем элементе для обеспечения свойства упорядоченности.

[1]   На третьей стадии (см. рис. 7.9, d-e) соединяются пары пирамид для сортировки трех ключей (созданных на второй стадии) и, добавляя новый ключ, формируется (п + 1)/8 пирамид, кажда[я из которых сортирует 7 ключей. Вновь добавленный ключ помещается в корень и для соблюдения свойства упорядоченности может быть заменен ключом, хранящимся в элементе-потомке:

Рис. 7.9. с 15 ключами: (а) пирамиды с одним ключом на нижнем уровне; (b-с) комбинирование этих пирамид в пирамиды для 3 ключей и затем (d-e) пирамиды для 7 ключей, до тех пор пока (f-g) не будет создан конечный вариант пирамиды. Прохождение ключей при нисходящей сортировке выделено штриховой линией

/. На стадии /, где 2 < / < h (рис. 7.9, f-g, где / = 4) соединяются пары пирамид для сортировки (2′ -1) ключей (созданных на предыдущей стадии) и, добавляя новый ключ, формируется (п + 1)/2′ пирамид, каждая из которых сортирует 2/_1 -1 ключей. Новый добавляемый ключ помещается в корень, но для соблюдения свойства упорядоченности может быть заменен ключом, хранящимся в элементе-потомке.

показано на рис. 7.9 для h = 4.

Можно описать восходящее построение как рекурсивный алгоритм, показанный во фрагменте кода 7.8, вызываемый передачей последовательности, хранящей ключи, для которых требуется выстроить пирамиду. Алгоритм построения описывается как действие над ключами и сопутствующими им элементами.

Алгоритм BottomUpHeap(5):

Input: последовательность 5, сортирующая п = 2Л-1 ключей.

Output: пирамида Т, сортирующая ключи в S.

if S пустая then

return пустую пирамиду (состоящую из единственного простого узла).

Удалить из S первый ключ /с.

Разбить S на две последовательности — S1 и каждая размером (л – 1)/2.

Г| <- Bottom UpHeap(S1)

Т2 <- BottomUpHeap(S2)

Создать бинарное дерево Г с корнем г, хранящим к, правую ветвь

и левую ветвь Г2.

Выполнить нисходящую сортировку от корня г дерева Т, если потребуется.

return Г

Фрагмент кода 7.8. Рекурсивное восходящее построение пирамиды

асимптотически быстрее, чем последовательный ввод п ключей в изначально пустую пирамиду, как это следует из приведенного ниже утверждения.

Утверждение 7.3. с п ключами занимает О(п) времени.

Доказательство. Для анализа восходящего построения применим «визуальный» подход, представленный на рис. 7.10.

Пусть Г — полная пирамида, v — составной узел Г, a T(v) — ветвь, корнем которой является v. Максимальное время формирования T(v) из двух рекурсивно реализованных ветвей, корнями которых являются дочерние элементы v, будет пропорционально высоте T(v). Это происходит в случае нисходящей сортировки от v вниз до самого нижнего простого узла T(v). Теперь рассмотрим путь/?(v) от узла v до простого узла, являющегося его потомком в Т, то есть путь, начинающийся в v, проходящий через правый дочерний элемент v, затем вниз по его левой ветви до тех пор, пока не будет достигнут простой узел. В принятой здесь терминологии этот путь р(у) ассоциируется с узлом v. Заметим при этом, что p{v) не обязательно соответствует пути, по которому выполняется нисходящая сортировка при формировании T(v). Совершенно ясно, что длина p{v) будет равна высоте T(v). Следовательно, формирование T{v) займет максимальное время, пропорциональное длине p(v). Таким образом, общее время выполнения восходящего построения пропорционально сумме длин путей, ассоциируемых с составными узлами Т.

Заметим также, что для любых двух составных узлов v и и в Гпути p(v) и р(и) не имеют общих дуг, хотя могут иметь общие узлы (см. рис. 7.10). Исходя из этого, сумма длин путей, ассоциируемых с составными узлами Ть не более количества дуг пирамиды Г, то есть не превышает 2п. Из этого следует: восходящее построение пирамиды Г занимает О(п) времени.

Рис. 7.10. Визуальное обоснование линейного времени выполнения восходящего построения пирамиды, где ассоциируемые с составными узлами пути выделены сплошной и штриховой линиями. Например, ассоциируемый с корнем путь включает составные узлы, хранящие ключи 4, 6, 7 и 11, и один простой узел

Резюмируем. Утверждение 7.3 устанавливает, что время выполнения первой стадии сортировки пирамиды может быть сокращено до О(п). К сожалению, время выполнения второй стадии асимптотически не может быть меньше 0(п log п) (то есть оно всегда равно О(п log п), даже в худшем случае). Доказательство этому проводится в главе 10.

Завершим главу обсуждением модели проектирования, позволяющей расширять АТД «очередь с приоритетами» для придания ей дополнительных свойств.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии