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

Пирамидальная сортировка в некотором роде является модификацией такого подхода, как сортировка выбором, с тем лишь отличием, что минимальный(или максимальный) элемент из неотсортированной последовательности выбирается не за O(n) операций, а за O(log n). Соответственно и производительность такого метода будет не ~ O(n²), а O(n*log n), т.е. наиболее быстрая для сортировки.

Естественно, без дополнительных манипуляций с неотсортированной последовательностью мы не добьемся выбора из нее максимального (в пирамидальной сортировке выбирается максимальный, поэтому дальше будем это всегда предполагать) элемента за O(log n). Точнее, для такого быстрого выбора из этой неотсортированной последовательности строится некоторая структура. И вот именно суть метода пирамидальной сортировки и состоит в построении такой структуры, называемой соответственно " пирамидой ".

Суть метода

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

Пирамида построена, далее можно начинать основные итерации сортировки. На каждой итерации:

1. Вынимаем вершину пирамиды

2. На ее место вставляем последний в пирамиде элемент

3. "Просеиваем" этот элемент сквозь пирамиду.

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

Просеивание

Неясным остался момент "просеивания" элемента сквозь пирамиду. Под этим подразумевается восстановление баланса пирамиды. После того как мы ставим последний элемент на вершину - пирамида теряет свои свойства, становится "разбалансированной". Поэтому дальше нужно этот элемент поставить в соответствующее ему место, а на вершину восстановить максимальный элемент.

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

Структура пирамиды

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

Например, имеем исходную последовательность:
x = [22, 100, 44, 15, 2, 36, 53, 23, 82, 5] Пирамида для нее будет выглядеть как:

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

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

x[i] >= max(x[2*i+1], x[2*i+2])

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

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

Может возникнуть вопрос: с чего это вдруг мы сразу пол-массива считаем за пирамиду, а не строим ее шаг за шагом начиная с последнего элемента, добавляя туда потом предпоследний и т.д. до первого элемента? Дело все в том, что для второй половины нашего исходного массива основное свойство пирамиды - выполняется автоматически. Вернее, оно не нарушается, поскольку для элементов второй половины просто уже не будет потомков!!! Действительно: потомки для всех x[i], где i = n/2..n будут соответственно x[n+1]...x[2*n+2], т.е. такие, которых в нашем массиве уже нет. А поэтому нет смысла для элементов второй половины строить пирамиду последовательно добавляя каждый элемент, т.к. в алгоритме текущий добавляемый элемент просто будет не с чем сравнивать, сыновей-то с такими индексами - просто нет!

Так что спокойно принимаем вторую половину нашей последовательности как пирамиду и приступаем к следующему этапу построения - добавлению элементов.

Чтобы добавить элемент в пирамиду - нужно поменять его с наибольшим ребенком, если последний превосходит добавляемый элемент. Затем тоже самое по отношению уже к новым его детям. Т.о. чтобы добавить в пирамиду новый элемент x[i], нужно:

1. Добавить элемент x[i] слева к массиву уже имеющейся пирамиды

2. Найти максимального из его сыновей: maxChild = max(x[2*i+1], x[2*i+2])

3. Если x[i] >= maxChild - завершение процедуры, элемент занимает положенное ему место, добавление завершено, иначе - шаг 4.

4. maxChild > x[i] - поменять их местами(т.е. поменять местами x[i] и его большего ребенка).
Перейти к шагу 2, учитывая новое положение добавляемого элемента.

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

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

Псевдокод: Восстановление баланса пирамиды при добавлении нового x[k] управление:

// алгоритм процедуры восстановления баланса пирамиды

// при добавлении нового x[k]

// В x[] - исходный массив

// n - количество его элементов

// k - индекс добавляемого/просеиваемого элемента

// Это чтобы при k=0 и n=0 не делалось лишней перестановки

 

if n = 0 then exit

tmp = x[i] // Оставляем копию

while k <= n/2 do

childPos = 2*k+1 // Индекс левого ребенка

// выбираем в childPos индекс большего ребенка

if (childPos < n) and (x[childPos] < x[childPos + 1]) then

childPos= childPos+1

 

// Если x[k] больше максимального ребенка- завершение

if(tmp >= x[childPos]) then

break;

// иначе - меняем его с наибольшим ребенком

else

x[k] = x[childPos];

k = childPos

endIf

end while

// В конце восстанавливаем просеянному элементу его первоначальное значение

x[k] = tmp;

end

Задание

1. Начертите бинарное дерево, корень которого имеет индекс 6, и которое представлено приведенными ниже полями.

Индекс	key	left	right
			NIL
			NIL
		NIL	NIL
		NIL	NIL
		NIL	NIL
		NIL	NIL

 

2. Каков будет порядок элементов списка [23,17,21,3,42,9,13,1,2,7,35] после применения к нему этапа построения пирамиды?

 

Алгоритмы поиска

 

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

Очевидно, что с отсортированными данными работать гораздо легче, чем с произвольно расположенными.

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