Будь умным!


У вас вопросы?
У нас ответы:) 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. Шутовской хоровод и Контрапункт относятся рассказы написанные в годы когда писатель жил в Италии 1923
2. психолога которой ставит эксперименты по проекции астральных тел во времени и простанстве
3. Питання з Історії Україн
4. С 2810 по 211 36 часов урока Время
5. тематика и филогения
6. В качестве аналогий иногда удается привлекать более поздние русские а также западноевропейские письменные
7. Тема- Основные понятия о морском транспорте и его пути.
8. court clerk 2 prosecutor 3 solicitor 4 brrister 5 biliff 6 defendnt 7 sheriff 8 witness 9 ppellnt 10 judge 11 plintiff 12 prison officers
9. БЕЛОРУСКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра НАУЧНАЯ РАБОТА
10.  три стандарти ISO і 2чотири ISO-TS
11. Кудрявый отчаянно крутил головой оглядываясь и пытался абстрагироваться от громкого нескончаемого крика
12. тема взглядов экономистов XV XVII вв
13. Я и все парни в Nickelbck большие поклонники Megdeth
14. реферат дисертації на здобуття наукового ступеня кандидата медичних наук Дніпропетровс
15. Ігрова діяльність у навчальному процесі початкової школи
16. Педагогической ассамблее которая проходила в январе в СанктПетербурге и открывала Год учителя был предс
17. е гг происходило усиление силовых наркоматов и карательнорепрессивного аппарата
18. 25 тыс.часов К какой области электромагнитных волн относится излучение с длиной волны 02 мкм Какую освещ
19. аузы толы б аз м~лшерде шырыштыірі~ді ~ш ~абатты в аз м~лшерде жабыс~а~ тот басандай г к~п м~лшерд
20. среднегодовая стоимость основных фондов предприятия среднегодовая стоимость машин и оборудования акти