2017-12-14
1319
Пирамидальное дерево– позволяет эффективно выполнять основные операции над очередями с приоритетами. Записи пирамидального дерева хранятся в массиве таким образом, что каждый ключ обязательно больше, чем значения ключей в двух других заданных позициях. В свою очередь, каждый из этих ключей должен быть больше, чем два других ключа и т.д.
Очередь с приоритетами — это структура данных, состоящая из элементов с ключами, которая поддерживает две основные операции: вставить (insert) новый элемент и извлечь (remove) элемент с наибольшим ключом.
Имеется возможность модифицировать так, чтобы сортировка массива не требовала дополнительной памяти — организовав пирамидальное дерево внутри сортируемого массива. Другими словами, перейдя к задаче сортировки, мы не будем скрывать очередь с приоритетами, и вместо того чтобы держаться в рамках интерфейса АТД очереди с приоритетами, будем непосредственно вызывать функции fixUp и fixDown.
Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Представлена на рисунке 8.
|
|
|
Рисунок 8
Код реализации:
#include <iostream>
void iswap (int&n1, int&n2) {
int temp = n1;
n1 = n2;
n2 = temp;
}
int main () {
unsigned const n = 100u;
int a[n];
// Для наглядности заполняем массив числами от n до 0.
for (unsigned i = 0u; i< n; ++i) {
a[i] = n - i;
std::cout<< a[i] << ' ';
}
// ----------- Сортировка ------------
// Сортирует по возрастанию. Чтобы получить сортировку по убыванию,
// поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
unsigned sh = 0u; // Смещение
bool b;
do {
b = false;
for (unsigned i = 0u; i< n; ++i) {
if (i * 2 + 2 + sh< n) {
if ((a[i + sh] > /*<*/ a[i * 2 + 1 + sh]) || (a[i + sh] > /*<*/ a[i * 2 + 2 + sh])) {
if (a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh]) {
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
} elseif (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh]) {
iswap(a[i + sh], a[i * 2 + 2 + sh]);
b = true;
}
}
// Дополнительная проверка для последних двух элементов;
// с её помощью можно отсортировать пирамиду
// состоящую всего лишь из трёх элементов
if (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh]) {
iswap(a[i * 2 + 1 + sh], a[i * 2 + 2 + sh]);
b = true;
}
} elseif (i * 2 + 1 + sh< n) {
if (a[i + sh] > /*<*/ a[ i * 2 + 1 + sh]) {
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
}
}
}
if (!b)
++sh; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
} while (sh + 2 < n); // Конец сортировки
std::cout<<std::endl<<std::endl;
for (unsigned i = 0u; i< n; ++i)
std::cout<< a[i] << ' ';
return 0;
}
