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

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

    В основе пирамидальной сортировки лежит специальный тип бинарного дерева, называемый пирамидой; значение корня в любом поддереве такого дерева больше, чем значение каждого из его потомков. Непосредственные потомки каждого узла не упорядочены, поэтому иногда левый непосредственный потомок оказывается больше правого, а иногда наоборот. Пирамида представляет собой полное дерево, в котором заполнение нового уровня начинается только после того, как предыдущий уровень заполнен целиком, а все узлы на одном уровне заполняются слева направо.
    Сортировка начинается с построения пирамиды. При этом максимальный элемент списка оказывается в вершине дерева: ведь потомки вершины обязательно должны быть меньше. Затем корень записывается последним элементом списка, а пирамида с удаленным максимальным элементом переформировывается. В результате в корне оказывается второй по величине элемент, он копируется в список, и процедура повторяется пока все элементы не окажутся возвращенными в список.
    Вот как выглядит соответствующий алгоритм:

сконструировать пирамиду
for i = 1 to N do
	скопировать корень пирамиды в список
	переформировать пирамиду
end for

Некоторые детали в этом алгоритме следует уточнить. Сначала мы должны определить, из чего состоят процедуры конструирования и переформирования пирамиды: это влияет на эффективность алгоритма.
Нас интересует реализация алгоритма. Накладные расходы на создание бинарного дерева растут с ростом списка. Можно, однако, воспользоваться местом, занятым списком. Можно "перестроить" список в пирамиду, если учесть, что у каждого внутреннего узла два непосредственных потомка, за исключением, быть может, одного узла на предпоследнем уровне. Следующее отображение позволяет сформировать требуемую пирамиду. Непосредственных потомков элемента списка с номером i будем записывать в позиции 2i и 2i + 1. Заметим, что в результате положения всех потомков будут различны. Мы знаем, что если 2i > N, то узел i оказывается листом, а если 2i = N, то у узла i ровно один потомок. На рисунке ниже изображена пирамида и ее списочное представление.

Переформирование пирамиды
При копировании наибольшего элемента из корня в список корневой узел остается свободным. Мы знаем, что в него должен попасть больший из двух непосредственных потомков, и мы должны рассмотреть, кто встает на его место, и так далее. При этом пирамида должна оставаться настолько близкой к полному дереву, насколько это возможно. Переформирование пирамиды мы начинаем с самого правого элемента на нижнем ее уровне. В результате узлы с нижней части дерева будут убираться равномерно. Если за этим не следить, и все большие значения оказываются в одной части пирамиды, то пирамида разбалансируется и эффективность алгоритма падает. Вот что получается в результате:

FixHeap(list, root, key, bound)
list				сортируемый список / пирамида
root				номер корня пирамиды
key				ключевое значение, вставляемое в пирамиду
bound			правая граница (номер) в пирамиде

vacant = root
while 2*vacant <= bound do
	largerChild = 2*vacant
	
	// поиск наибольшего из двух непосредственных потомков
	if (largerChild < bound) and 
		(list[largerChild + 1] > list[largerChild + 1]) then
		largerChild = largerChild + 1
	end if
	
	// находится ли ключ выше текущего потомка?
	if key > list[largerChild] then
		// да, цикл завершается
		break
	else
		// нет, большего непосредственного потомка
		// следует поднять
		list[vacant]	 = list[largerChild]
		vacant = largerChild
	end if
end while
list[vacant]	 = key

При взгляде на параметры этого алгоритма у Вас мог возникнуть вопрос, зачем нужна переменная root. Действительно, поскольку процедура не рекурсивна, корень пирамиды всегда должен быть первым элементом. Мы увидим, однако, что этот дополнительный параметр позволит нам строить пирмиду снизу вверх. Значение правой границы введено потому, что при переписывании элементов из пирамиды в список пирамида сжимается.

Построение пирамиды
Наш подход к функции FixHeap позволяет сформировать начальное состояние пирамиды. Любые два значения можно считать листьями свободного узла. Поскольку все элементы являются листьями, нет необходимости делать что-либо со второй половиной списка. Мы можем просто делать из листьев маленькие пирамиды, а затем постепенно собирать их вместе, пока все значения не попадут в список. Следующий цикл позволяет реализовать эту процедуру:

for i = N/2 down to 1 do
	FixHeap(list, i, list[i], N)
end for

Окончательный алгоритм
Сложив вместе написанные куски и добавив необходимые операции по перенесению элементов из пирамиды в список, мы получаем окончательный алгоритм:

for i = N/2 down to 1 do
	FixHeap(list, i, list[i], N)
end for
for i = N down to 2 do
	max = list[1]
	FixHeap(list, 1, list[i], i - 1)
	list[i] = max
end for

Сайт управляется системой uCoz