|
====================================================================
> 9. Описание и исходник HeapSort (пирамидальная сортировка).
====================================================================
Рассмотрим слегка модифицированную сортировку выбором:
A[1..N] - сортируемый массив из n элементов.
for ( i=N; i>1; i--)
Hайти наибольший из элементов 1..i и
поменять его местами с i-м.
Пример действий для случайного массива A[1..8]
44 55 12 42 94 18 06 67 исходный массив
i=8 44 55 12 42 67 18 06 |94 94 <-> 67
i=7 44 55 12 42 06 18 |67 94 67 <-> 06
i=6 44 18 12 42 06 |55 67 94 55 <-> 18
i=5 06 18 12 42 |44 55 67 94 44 <-> 06
i=4 06 18 12 |42 44 55 67 94 42 <-> 42
i=3 06 12 |18 42 44 55 67 94 18 <-> 12
i=2 06 |12 18 42 44 55 67 94 12 <-> 12
Вертикальной чертой отмечена граница уже отсортированной части
массива.
Очевидно, быстродействие алгоритма можно оценить как Omega(N^2),
так как выбор наибольшего элемента на каждом шаге требует Omega(N)
операций.
Построим структуру данных, позволяющую выбирать максимальный
элемент за O(logn) времени. Тогда общее быстродействие сортировки
будет O(nlogn).
Эта структура также должна позволять быстро вставлять новые элементы
(чтобы быстро ее построить из исходного массива) и удалять максимальный
элемент (он будет помещаться в уже отсортированный конец массива).
Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором
- все узлы имеют глубину k или k-1 - дерево сбалансированное.
- при этом уровень k-1 полностью заполнен, а уровень k заполнен
слева направо.
- выполняется 'свойство пирамиды': каждый элемент <= родителя.
Пример 1:
h1 Общий вид пирамиды высоты k=4
/ \
/ \ 'Свойство пирамиды' при такой картинке
/ \ можно записать в виде
/ \ h_i >= h_2i
/ \ h_i >= h_2i+1
/ \
h2 h3
/ \ / \
/ \ / \
/ \ / \
h4 h5 h6 h7 } 3 уровень
/ \ / \ /
h8 h9 h10 h11 h12 } 4 уровень, заполнен слева направо.
Пример 2:
94
/ \
/ \
/ \
/ \
/ \
55 44
/ \ / \
/ \ / \
06 42 18 12
Как хранить пирамиду? Проще всего поместить ее в массив.
Схема соответствия: В массиве именно пирамида:
A[1] - корень дерева | Для массива, представляющего
A[2i] - левый сын A[i] | пирамиду, A[i] >= A[2i]
A[2i+1] - правый сын A[i] | A[i] >= A[2i+1]
Для примера 2 массив будет 94 55 44 6 42 18 12.
Плюсы такого подхода очевидны:
- для хранения пирамиды не нужно никакой специальной структуры,
никаких дополнительных переменных, нужно лишь понимать схему.
- узлы хранятся от вершины и далее вниз, уровень за уровнем.
- узлы одного уровня хранятся в массиве слева направо.
Далее я часто буду говорить, что задана пирамида, давая
ее в виде массива.
Восстановить ее как геометрический объект легко - достаточно
вспомнить схему хранения. Hа примере 1 (см. выше) показана
пирамида, восстановленная из массива h[1..12].
Фаза 1 сортировки: построение пирамиды
Если у нас уже готова пирамида a[k+1..N] - можно расширить ее до
пирамиды a[k..N], проведя для a[k] процедуру добавления элемента.
Процедура добавления элемента в готовую пирамиду
1. Hовый элемент Х помещаем в вершину дерева.
2. Смотрим на сыновей слева и справа - выбираем
наибольший.
3. Если этот элемент больше Х - меняем их местами и идем у
шагу 2 уже относительно сына. Иначе конец процедуры.
Реализация процедуры на Си:
downHeap(int a[], int k, int N)
/* До процедуры: a[k+1..N] - пирамида */
/* После: a[k..N] - пирамида */
{ int newElt, child;
newElt=a[k];
while(k <= N/2) /* k has child(s) */
{ child = 2*k;
/* pick larger child */
if(child < N && a[child] < a[child+1])
child++;
if(newElt >= a[child]) break;
/* else */
a[k] = a[child]; /* move child up */
k = child;
}
a[k] = newElt;
}/*downHeap*/
Учитывая, что высота пирамиды h <= log N, downheap требует O(logN)
времени. 2
Пусть дан произвольный массив a[1..N], который надо отсортировать.
Hачать построение пирамиды можно с a[k..N], k = [N/2]
Этот массив обладает свойством пирамиды, так как для него не
существует индексов i,j: j = 2*i ( или j = 2*i+1 ).
Далее расширяем ее, по очереди вызывая downheap для остальных элементов
справа налево:
for(i=N/2; i >= 1; i--) downHeap(a, i, N);
Вот иллюстрация процесса для пирамиды из 8-и элементов:
44 55 12 42 // 94 18 06 67 справа - часть массива,
44 55 12 // 67 94 18 06 42 начинающаяся с k=8/2=4
44 55 // 18 67 94 12 06 42
44 // 94 18 67 55 12 06 42 остальные элементы добавляются
// 94 67 18 44 55 12 06 42 один за другим, справа налево.
Фаза 2: собственно сортировка
Берем верхний элемент пирамиды (первый в массиве) - меняем
с последним местами, затем вызываем downheap для построения
пирамиды из оставшегося массива a[1..N-1].
downheap(a, 1, N-1)
То есть кладем бывший последний элемент массива на вершину
вместо снятого и передвигаем его на нужное место, восстанавливая
пирамидальность.
При этом, как мы и хотели (!), максимальный элемент придет на
вершину(первое место в массиве) всего за log_2(N) операций.
Меняем местами верхний элемент пирамиды (первый в массиве) и
последний в текущем массиве (т.е уже (N-1)-ый).
И так далее, всего N шагов.
for(i=N; i > 1; i--)
{ temp = a[i];
a[i]=a[1]; /* largest of a[1..i] */
a[1]=temp;
downHeap(a,1,i-1); /* restore a[1..i-1] heap */
}
Иллюстрация на нашем массиве, уже построенном в пирамиду.
94 67 18 44 55 12 06 42 //
67 55 44 06 42 18 12 // 94
55 42 44 06 12 18 // 67 94
44 42 18 06 12 // 55 67 94
42 12 18 06 // 44 55 67 94
18 12 06 // 42 44 55 67 94
12 06 // 18 42 44 55 67 94
06 // 12 18 42 44 55 67 94
Исходник сортировки целиком:
heapSort(int a[], int N)
/* sort a[1..N], N.B. 1 to N */
{ int i, temp;
for(i=N/2; i >= 1; i--)
downHeap(a, i, N);
/* a[1..N] is now a heap */
for(i=N; i > 1; i--)
{ temp = a[i];
a[i]=a[1]; /* largest of a[1..i] */
a[1]=temp;
downHeap(a,1,i-1); /* restore a[1..i-1] heap */
}
}/*heapSort*/
Для построения пирамиды нашим способом требуется NlogN операций,
затем мы N-1 раз вызываем downheap, таким образом общее быстродействие -
P(NlogN).
Прекрасной характеристикой этого метода является то, что
среднее число пересылок - (N*log N)/2, и отклонения от этого
значения сравнительно малы.
P.S Существует два метода Heapsort, одинаковых по общему
быстродействию. Выше я изложил только один из них, более короткий
в описании. В частности, фазу построения начальной пирамиды можно
завершить и за O(N) операций.
|
