Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Последовательного заполнения пирамиды

Пирамидальная сортировка

Построение пирамиды

Существуют разные подходы, рассмотрим некоторые

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

Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т.е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).

Удобнее всего поместить пирамиду в массив. При этом распределение индексов массива по узлам дерева будет выглядеть так (на этом рисунке все цифры - это индексы элементов массива, а ни в коем случае не значения этих элементов):

 

Рисунок 1.

Таким образом, для того, чтобы каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].

Более подробно

ИТАК, пирамида – это бинарное дерево высоты k, в котором

- все узлы имеют глубину k или k-1 - дерево сбалансированное.

- при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид:

- выполняется "свойство пирамиды": каждый элемент меньше, либо равен родителю.

Как хранить пирамиду? Наименее хлопотно - поместить ее в массив.

Первый подход

Порядок заполнения для 94 67 18 44 55 12 06 42.

Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме:

- в a[0] хранится корень дерева;

- левый и правый сыновья элемента a[i] хранятся, соответственно, в a[2i+1] и a[2i+2]

Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2].

Плюсы такого хранения пирамиды очевидны:

- никаких дополнительных переменных, нужно лишь понимать схему.

- узлы хранятся от вершины и далее вниз, уровень за уровнем.

- узлы одного уровня хранятся в массиве слева направо.

Запишем в виде массива пирамиду, изображенную выше.

Слева-направо, сверху-вниз:

94 67 18 44 55 12 06 42.

На рисунке место элемента пирамиды в массиве обозначено цифрой справа-вверху от него.

Восстановить пирамиду из массива как геометрический объект легко - достаточно вспомнить схему хранения и нарисовать, начиная от корня.

Идея алгоритма

Пирамида — двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.

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

Самый большой элемент пирамиды находится в её вершине.

Отделяем вершинный элемент, и записываем его в конец результирующего массива.

На место вершинного элемента записываем элемент из самого нижнего уровня дерева.

Восстанавливаем (пересортировываем) пирамиду.

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

Весь фокус алгоритма в том, что пирамида без дополнительных затрат хранится прямо в исходном массиве. По мере того, как размер пирамиды уменьшается, она занимает всё меньшую часть массива, а результат сортировки записывается начиная с конца массива на освободившиеся от пирамиды места.

 

Алгоритм

последовательного заполнения пирамиды

В полностью отсортированном массиве каждый следующий элемент больше предыдущего (и, значит, больше всех предыдущих). Пирамида же - это частично отсортированный массив. В ней элемент номер i больше элементов с номерами и (элементы нумеруются с нуля). Соответственно, построение пирамиды сводится к особой сортировке массива, чтобы выполнялось это свойство. При этом такая «неполная» сортировка делается гораздо быстрее, чем полная сортировка массива, так как отсортированные цепочки короткие.

Допустим, у нас имеется последовательность чисел:

1, 4, 2, 7, 8, 0, 5, 2, 6.

 

Чтобы построить пирамиду, нужно добиться, чтобы все элементы номер i были больше элементов номер и . Например, нулевой элемент должен быть больше первого и второго.

Отсчет i=0.Тогда левый элемент будет иметь номер 1, так как 2*0+1=1, а правый 2*0+2=2.

Нулевой элемент должен быть больше первого и второго.

В нашем примере это не так, поэтому поменяем нулевой элемент и первый:

4, 1, 2, 7, 8, 0, 5, 2, 6.

i=1, номер 3 и номер 4

Первый элемент (единица) должен быть больше третьего (семёрки) и четвёртого (восьмёрки). Для этого поменяем местами единицу и восьмёрку:

4, 8, 2, 7, 1, 0, 5, 2, 6.

Поменяем местами нулевой и первый элементы, чтобы восстановить порядок в начале:

8, 4, 2, 7, 1, 0, 5, 2, 6.

Снова первый и третий не в порядке. Поменяем местами четвёрку и семёрку:

8, 7, 2, 4, 1, 0, 5, 2, 6.

i=2, номер 5 и номер 6

Второй элемент (двойка) должен быть больше пятого (нуля) и шестого (пятёр­ки). Это не так. Поменяем местами двойку и пятёрку:

8, 7, 5, 4, 1, 0, 2, 2, 6.

Аналогично, четвёрка должна быть больше последних двойки и шестёрки. Поменяем местами четвёрку и шестёрку:

8, 7, 5, 6, 1, 0, 2, 2, 4.

Последние пять элементов не с чем сравнивать; их мы не трогаем. Теперь свойство пирамиды выполнено для всех элементов. Пирамида построена.

Обрати внимание, что пятёрка никак не связана с шестёркой, поэтому они остаются в «неправильном» порядке (по возрастанию, а не по убыванию, как мы сейчас хотим).

После того, как пирамида построена, из неё можно получить полностью отсортированный массив. Особенность пирамиды в том, что в её вершине (нулевой элемент) находится максимальный элемент среди всех элементов пирамиды. Но максимальный элемент должен быть в конце массива. Поменяем местами нулевой и последний элементы, и больше не будем последний элемент считать частью пирамиды:

4, 7, 5, 6, 1, 0, 2, 2 | 8.

Пирамида при этом нарушается. Восстанавливаем её так, как строили вначале (восьмёрку при этом не учитываем):

7, 6, 5, 4, 1, 0, 2, 2 | 8.

Снова самый большой элемент пирамиды находится вначале. Этот элемент — самый большой из оставшихся слева от восьмёрки. Поэтому он дол­жен быть перед ней. Меняем местами нулевой элемент и последний элемент пирамиды, и отделяем последний элемент от пирамиды:

2, 6, 5, 4, 1, 0, 2 | 7, 8.

Восстанавливаем пирамиду:

6, 4, 5, 2, 1, 0, 2 | 7, 8.

Меняем местами начальный и последний элементы пирамиды, отделяем последний элемент:

2, 4, 5, 2, 1, 0 | 6, 7, 8.

Восстанавливаем пирамиду:

5, 4, 2, 2, 1, 0 | 6, 7, 8.

Меняем местами начальный и последний элементы пирамиды, отделяем последний элемент:

0, 4, 2, 2, 1 | 5, 6, 7, 8.

Восстанавливаем пирамиду:

4, 2, 2, 0, 1 | 5, 6, 7, 8.

 

Меняем местами начальный и последний элементы пирамиды, отделяем последний элемент:

1, 2, 2, 0 | 4, 5, 6, 7, 8.

Восстанавливаем пирамиду:

2, 1, 2, 0 | 4, 5, 6, 7, 8.

Меняем местами начальный и последний элементы пирамиды, отделяем последний элемент:

0, 1, 2 | 2, 4, 5, 6, 7, 8.

Восстанавливаем пирамиду:

2, 1, 0 | 2, 4, 5, 6, 7, 8.

Меняем местами начальный и последний элементы пирамиды, отделяем последний элемент:

0, 1 | 2, 2, 4, 5, 6, 7, 8.

Восстанавливаем пирамиду:

1, 0 | 2, 2, 4, 5, 6, 7, 8.

Меняем местами начальный и последний элементы пирамиды, отделяем последний элемент:

0 | 1, 2, 2, 4, 5, 6, 7, 8.

В пирамиде остался единственный элемент. Он самый маленький из всех. Просто присоединяем его к массиву:

0, 1, 2, 2, 4, 5, 6, 7, 8.

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.