Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
27.
Алгоритм выбора из пирамиды
Определение 1. Почти полным двоичным деревом будем называть двоичное дерево, для которого существует такое целое число h ≥ 0, что:
Определение 2. Будем называть пирамидой размера n почти полное двоичное дерево с n узлами, для которого содержимое каждого узла не больше содержимого отца этого узла.
На рис. 3. приведён пример пирамиды размера 12, построенной из последовательности элементов 75, 80, 90, 5, 10, 4, 60, 2, 15, 0, 85, 65.
Определение 3. Кучей называется массив k из n элементов, для которого выполняются условия для всех 1 ≤ j < n. ()((1)/2)kjkj
Если пирамида реализуется с помощью массива, то такой массив является кучей. Элемент k(0) является корнем дерева. Отметим, что значение потомка в куче не превосходит значения предка. Таким образом, наибольший элемент дерева (или любого поддерева) находится в корневой вершине дерева (поддерева).
Движение по дереву осуществляется следующим образом:
В дереве, составляющем кучу, все уровни (кроме, может быть, последнего) заполнены полностью. Поэтому высота этого дерева равна O(log n), где n – число элементов в куче. Как будет показано ниже, количество основных операций над кучей пропорционально высоте дерева и, следовательно, составляет O(log n).
Алгоритм пирамидальной сортировки состоит из двух этапов:
Рассмотрим первый этап, для чего создадим некоторую функцию, позволяющую сформировать кучу. Пусть её параметрами являются массив k и i – индекс элемента. Предположим, что поддеревья с корнями k(2i + 1) и k(2i + 2) удовлетворяют условиям кучи. Рассмотрим в качестве текущего элемента их отца k(i). Если для него свойство кучи не выполняется, то значение k(i) следует поменять со значением большего из его сыновей (например, с k(2i + 1)). Теперь текущим узлом становится узел k(2i + 1). Процесс формирования кучи продолжается до тех пор, пока значение текущего элемента меньше значения максимального из его сыновей и массив не закончится. Реализация восстановления свойства кучи с корнем в k(i) на примере целочисленного массива размера n представлена в листинге 2.
Листинг 2. Функция, восстанавливающая свойство кучи
template <typename T>
void HeapDown(T * k, int n, int i) {
int j;
T w;
while (2*i +1 < n) {
j = 2*i + 1;
if ((j + 1) < n && k[j] < k[j + 1]) ++j;
if (k[i] < k[j]) {
w = k[i];
k[i] = k[j];
k[j] = w;
i = j;
}
else return;
}
return;
}
Опишем процесс построения кучи снизу вверх из произвольного массива k. Для этого будем использовать функцию HeapDown(k, n,i ), применяя ее последовательно к элементам массива с индексами i = [(n – 2)/2], [(n – 2)/2] – 1, …, 0. К элементам с индексами [(n – 2)/2] + 1, …, n – 1 функция HeapDown не применяется, поскольку они являются листьями, то есть одноэлементными кучами. В результате преобразований куча построена и элемент k(0) содержит наибольшее значение среди сортируемых элементов. Порядок просмотра вершин гарантирует, что каждый раз при вызове функции свойства кучи для поддеревьев будет выполнены.
Второй этап алгоритма предусматривает перестроение кучи и формирование отсортированного массива. Значение элемента k(0) меняется местами со значением элемента k(n – 1), поскольку максимальный элемент должен стоять в конце отсортированного массива. В дальнейшей работе алгоритма элемент k(n – 1) участвовать уже не будет. В результате получаем массив длины n – 1, все элементы которого, за исключением значения k(0), удовлетворяют свойствам кучи. С помощью функции HeapDown(k, n-1,0 ) формируем кучу на первых (n – 1)-ом элементах массива. Текущее значение k(0) меняется теперь уже со значением элемента k(n – 2), вновь используем HeapDown(k, n-2,0 ) и получаем кучу из (n – 2)-х элементов и т.д. После того, как в уменьшающейся по размеру куче останется один элемент, алгоритм заканчивает работу. В итоге массив k содержит упорядоченные по возрастанию элементы.
Реализация на С++ алгоритма пирамидальной сортировки фрагмента массива k элементов типа T с k(left) по k(right) представлена в листинге 3.
Листинг 3. Алгоритм пирамидальной сортировки
template <typename T>
void HeapSort(T * k, int left, int right) {
int j, n = right – left + 1;
T temp;
T * pq = k + left;
// Построение пирамиды
for (j = (n – 2)/2; j >= 0; --j)
HeapDown(pq, n, j);
// Перестройка пирамиды
while(n > 1) {
temp = pq[0];
pq[0] = pq[n - 1];
pq[--n] = temp;
HeapDown(pq, n, 0);
}
}
Вычислительная сложность алгоритма
Чтобы определить вычислительную сложность алгоритма пирамидальной сортировки, заметим, что почти полное двоичное дерево с n узлами имеет log2(n1)уровней. При создании пирамиды и при её перестройке каждая запись сравнивается, в худшем случае, с одним узлом на каждом уровне.
Максимальная вычислительная сложность алгоритма
Tmax(n) = TС(n) + TП(n), где TС(n) – вычислительная сложность создания пирамиды, TП(n) – вычислительная сложность перестройки пирамиды и получения отсортированного массива.
Вычислительная сложность создания пирамиды составляет