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

1. Вступление

2-3 куча это массив 2-3 деревьев, обладающих свойствами куч(родитель больше(меньше) всех своих детей).
2-3 дерево это сбалансированное дерево, родительский узел которого может иметь как два, так и три сына.
2-3 кучи применяются для реализации очередей с приоритетом и являются оптимизацией Фибоначчиевых куч
Применяются для оптимизации алгоритмов на графах, работы с очередями,моделирования
100
36
7
Куча на примере бинарной
3
19
25
2
17
1
Одно из деревьев 2-3 кучи
2-3 дерево

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

Зависимость количества операций балансировки от длины списка
250
Количество операций
200
150
100
50
0
0
20
40
60
Длина списка
80
100
120

3. Структура 2-3 кучи

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