Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков.
В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-куча, поскольку корень поддерева является максимумом из значений элементов поддерева.
В качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами.
Двоичную кучу удобно хранить в виде одномерного массива, причем
- левый потомок вершины с индексом i имеет индекс 2*i+1,
- правый потомок вершины с индексом i имеет индекс 2*i+2.
Корень дерева (кучи) – элемент с индексом 0.
Высота двоичной кучи равна высоте дерева, то есть
log2 (N+1)↑,
где N – количество элементов массива, ↑ – округление в большую сторону до ближайшего целого.
Для представленной кучи
log2 (10+1)↑ = 3,46↑ = 4
Способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма оценивается как
N·log2N.
Можно построить кучу за N шагов. Для этого сначала следует построить дерево из всех элементов массива, не заботясь о соблюдении основного свойства кучи, а потом вызвать метод упорядочения для всех вершин, у которых есть хотя бы один потомок (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
Потомки гарантированно есть у первых heapSize/2 вершин, где heapSize – размер кучи.
Реализация класса кучи
2
3
4
5
6
7
8
9
10
11
12
static const int SIZE = 100; // максимальный размер кучи
int *h; // указатель на массив кучи
int HeapSize; // размер кучи
public:
Heap(); // конструктор кучи
void addelem(int); // добавление элемента кучи
void outHeap(); // вывод элементов кучи в форме кучи
void out(); // вывод элементов кучи в форме массива
int getmax(); // удаление вершины (максимального элемента)
void heapify(int); // упорядочение кучи
};
Конструктор кучи
2
3
4
h = new int[SIZE];
HeapSize = 0;
}
Добавление элемента кучи
Новый элемент добавляется на последнее место в массиве, то есть позицию с максимальным индексом.
Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае новый элемент «поднимается» на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи.
Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна log2 N.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int i, parent;
i = HeapSize;
h[i] = n;
parent = (i-1)/2;
while(parent >= 0 && i > 0) {
if(h[i] > h[parent]) {
int temp = h[i];
h[i] = h[parent];
h[parent] = temp;
}
i = parent;
parent = (i-1)/2;
}
HeapSize++;
}
Вывод элементов кучи
Вывод элементов в форме кучи
2
3
4
5
6
7
8
9
10
11
12
int i = 0;
int k = 1;
while(i < HeapSize) {
while((i < k) && (i < HeapSize)) {
cout << h[i] << " ";
i++;
}
cout << endl;
k = k * 2 + 1;
}
}
Вывод элементов кучи в форме массива
2
3
4
5
6
for(int i=0; i< HeapSize; i++) {
cout << h[i] << " "; }
cout << endl;
}
Упорядочение кучи
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int left, right;
int temp;
left = 2*i+1;
right = 2*i+2;
if(left < HeapSize) {
if(h[i] < h[left]) {
temp = h[i];
h[i] = h[left];
h[left] = temp;
heapify(left);
}
}
if(right < HeapSize) {
if(h[i] < h[right]) {
temp = h[i];
h[i] = h[right];
h[right] = temp;
heapify(right);
}
}
}
В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав метод упорядочения для корня, то есть упорядочив все дерево.
Удаление вершины кучи (максимального элемента)
2
3
4
5
6
7
8
int x;
x = h[0];
h[0] = h[HeapSize-1];
HeapSize—;
heapify(0);
return(x);
}
Создать бинарную кучу из 16 элементов. Определить максимальный элемент.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Heap heap;
int k;
system("chcp 1251");
system("cls");
for(int i=0; i<16; i++) {
cout << "Введите элемент " << i+1 << ": ";
cin >> k;
heap.addelem(k);
}
heap.outHeap();
cout << endl;
heap.out();
cout << endl << "Максимальный элемент: " << heap.getmax();
cout << endl << "Новая куча: " << endl;
heap.outHeap();
cout << endl;
heap.out();
cout << endl << "Максимальный элемент: " << heap.getmax();
cout << endl << "Новая куча: " << endl;
heap.outHeap();
cout << endl;
heap.out();
cin.get();cin.get();
return 0;
}
Результат выполнения
Вопрос по функции "addelem".
Разве мы не можем после "if" добавить "else break;"? Если можем — почему не добавить? просто с Вашей реализацией даже при добавлении самого маленького элемента цикл всё равно будет проходить до корня дерева, но зачем нам это? Или я что-то упустил?
Думаю, можно добавить — ничего не должно нарушиться.
Пожалуйста, докажите, что потомки i-го элемента будут иметь номера 2i+1 и 2i+2
Для нулевого элемента потомки имеют номера 2*0+1=1 и 2*0+2=2.
Для элемента 1 потомки имеют номера 2*1+1=3 и 2*1+2=4. Так для каждого.
В функции heapify что передается в i
Номер элемента вершины, относительно которого производится упорядочивание
Лен! А ты можешь рассмотреть avl дерево?
Володя, теоретически да, но на это нужно время.
Можешь помочь, не возражаю)
А материал надо на C++ делать? А то у меня сейчас есть для языка Java.
На этом сайте только C++. Другие языки только в комментариях изредка встречаются.
а тебе нужно ? у меня есть реализация на java могу скинуть