Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Почти полным двоичным деревом будем называть двоичное дерево для которого существует такое целое число h

Работа добавлена на сайт samzan.ru: 2016-03-05


27.

Алгоритм выбора из пирамиды

Определение 1. Почти полным двоичным деревом будем называть двоичное дерево, для которого существует такое целое число h ≥ 0, что:

  1.  1. каждый лист дерева находится на уровне (h – 1) или h;
  2.  2. уровень (h – 1) максимально заполнен узлами;
  3.  3. все листья уровня h максимально смещены влево.

Определение 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) является корнем дерева. Отметим, что значение потомка в куче не превосходит значения предка. Таким образом, наибольший элемент дерева (или любого поддерева) находится в корневой вершине дерева (поддерева).

Движение по дереву осуществляется следующим образом:

  1.  1) предком элемента k(i) является k([(i – 1)/2]);
  2.  2) левым сыном k(i) является k(2i + 1);
  3.  3) правым сыном k(i) является k(2i + 2).

В дереве, составляющем кучу, все уровни (кроме, может быть, последнего) заполнены полностью. Поэтому высота этого дерева равна O(log n), где n – число элементов в куче. Как будет показано ниже, количество основных операций над кучей пропорционально высоте дерева и, следовательно, составляет O(log n).

Алгоритм пирамидальной сортировки состоит из двух этапов:

  1.   построение кучи из произвольного массива k;
  2.   перестроение кучи и формирование отсортированного массива.

Рассмотрим первый этап, для чего создадим некоторую функцию, позволяющую сформировать кучу. Пусть её параметрами являются массив 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) – вычислительная сложность перестройки пирамиды и получения отсортированного массива.

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




1. а Подготовили Учитель ' дефектолог Первой категории Дёмина Натал
2. Андорр
3. Российский государственный профессиональнопедагогический университет Институт экономики и управления
4. SUBJECTIVUS Жалобы на тяжесть в правом подреберье на головную боль возникающую к вечеру нарушение аккомодации
5. ТЕМА 10 УЧЕНИК КАК СУБЪЕКТ ВОСПИТАНИЯ 10
6. Роль и функции валютного рынка и валютного регулирования в современной российской экономике
7. I Rzeczowniki rodzju m~skiego mj~ dwie podstwowe grupy- njliczniejsz jest grup wyrz~w ko~cz~cych si~ n sp~~g~osk~-brt kot ch~opiec zeszyt b~l; i nieliczn- n smog~osk~ -
8. Путешествие в страну знаний Разработала музыкальный р
9. Историкопедагогический анализ инновации в современном образовании Теоретические вопросы 1
10. Единственный в своем роде
11. Краснодарский муниципальный медицинский институт высшего сестринского образования Вопросы к экзаме
12. И Сатпаев Андроновская культура Зыряновск Жезказган Каркаралы Акшатау 1 милли
13. Март Москва РостовнаДону 2003 ББК 67
14. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ К ПрАКТИЧЕСКОМУ ЗАНЯТИЮ ДЛЯ СТУДЕНТОВ Тема 2
15.  О порядке привлечения иностранных рабочих в г
16. Эпоха великих реформ
17. Валентины и Валентинки 1й ведущий- Высоким чувством окрылённыйКогдато в давние годаПридумал кто ~ т.html
18. I Повести В тупике- Роман
19. Влияние температуры на пластичность металла
20. отчет по перманентным долгам До 10го числа сдать служебную записку по бонусам для службы До 10го числа к