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

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

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

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

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

Если в исходном массиве 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.

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