Кучи. Применение

Проблема Фибоначчиевых куч

Структура 2-3 кучи
Степень дерева – высота корневого узла
Насыщенность дерева – возможность добавлять в дерево вершины без увеличения его степени
Деревья бывают насыщенные(t) и ненасыщенные(f)
В куче хранится массив деревьев по следующему принципу:
В i-ой ячейке дерева располагается только дерево степени i
Куча из 16 элементов
(общий вид)

Примеры деревьев
Тип
Внешний вид 2-3 дерева
Общий внешний вид
1
1
2
1
3
2
1
4
5
6
3
2
1
2
3
6
5
4
7
8
9
1
4
7
9
8
6
5
2
3
10
13
16
11 12
14 15
17 18

Общая схема элемента
Для большей конкретности рассмотрим 1f дерево:
NULL
NULL
NULL
NULL
NULL
NULL
K
K
K
V
V
V
pt
pt
pr
pr
ch
ch
ch
ln
rn
K (key) – ключ, определяет приоритет элемента
V(value) – значение
pr(parent) – родительский узел, элемент с более высоким
приоритетом.
pt(partner) – партнерский узел
ln(left neighbor) – левый сосед
rn(right neighbor) – правый сосед
сh(child) – дочерний узел, элемент с
более низким приоритетом

Вставка в кучу(O(1))
Вставка
Размещение
Слияние
Через партнера
Через сына
Делением
Когда дерево пустое
0f+0f
0f+0t
0t+0t

Пример вставки
1) Через партнера
1
2
1
2
+
=
0f
0f
0t
nf + nf = nt
2) Через сына
1
2
3
1
2
3
+
=
0f
0t
1f
nf + nt = (n+1)f
3) Делением
1
2
3
4
1
2
3
4
+
=
0t
0t
0f
1f
nt + nt = nf + (n+1)f

Извлечение из кучи минимума(O(log N))
Для извлечения из кучи минимума(это корневая вершина) сначала найдем нужное дерево,
а затем разложим дерево на составляющие по правилу:
nf = (n-1)f + (n-1)t
nt = nf + nf
Раскладываем до тех пор пока не получим дерево из одной вершины. Далее вставляем
части заново.
Пример:
2t = 2f + 2f = 1f + 1t + 2f = 0f + 0t + 1t + 2f
1
4
7
9
8
6
5
2
3
10
13
16
11 12
14 15
17 18
1
2
3
6
5
4
7
8
9
10
13
16
11 12
14 15
17 18
10
13
16
11 12
14 15
17 18
6
5
4
7
8
9
1
3
2
10
13
16
11 12
14 15
17 18
6
5
4
7
8
9
3
2
1
=
=
=

Сравнение асимптотик для различных куч

Зависимости количества вершин
в графе от скорости расчета