2015-08-12
451
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);
}
}
