Разделы презентаций


Вступление

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

Слайды и текст этой презентации

Слайд 1Вступление
2-3 куча это массив 2-3 деревьев, обладающих свойствами куч(родитель больше(меньше)

всех своих детей).
2-3 дерево это сбалансированное дерево, родительский узел которого

может иметь как два, так и три сына.
2-3 кучи применяются для реализации очередей с приоритетом и являются оптимизацией Фибоначчиевых куч
Применяются для оптимизации алгоритмов на графах, работы с очередями,моделирования

Куча на примере бинарной

2-3 дерево

Одно из деревьев 2-3 кучи

36

25

19

17

7

3

2

1

100

Вступление2-3 куча это массив 2-3 деревьев, обладающих свойствами куч(родитель больше(меньше) всех своих детей).2-3 дерево это сбалансированное дерево,

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

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

Слайд 3Структура 2-3 кучи
Степень дерева – высота корневого узла
Насыщенность дерева –

возможность добавлять в дерево вершины без увеличения его степени
Деревья бывают

насыщенные(t) и ненасыщенные(f)
В куче хранится массив деревьев по следующему принципу:

В i-ой ячейке дерева располагается только дерево степени i

Куча из 16 элементов
(общий вид)

Структура 2-3 кучиСтепень дерева – высота корневого узлаНасыщенность дерева – возможность добавлять в дерево вершины без увеличения

Слайд 4Примеры деревьев
Тип
Внешний вид 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

Примеры деревьевТипВнешний вид 2-3 дереваОбщий внешний вид11213214563212365478914798652310131611 1214 1517 18

Слайд 5Общая схема элемента
Для большей конкретности рассмотрим 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) – дочерний узел, элемент с
более низким приоритетом
Общая схема элементаДля большей конкретности рассмотрим 1f дерево:NULLNULLNULLNULLNULLNULLKKKVVVptptprprchchchlnrnK (key) – ключ, определяет приоритет элементаV(value) – значениеpr(parent) –

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

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

Слайд 7Пример вставки
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
Пример вставки1) Через партнера1212+=0f0f0tnf + nf = nt2) Через сына123123+=0f0t1fnf + nt = (n+1)f3) Делением12341234+=0t0t0f1fnt + nt

Слайд 8Извлечение из кучи минимума(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

=

=

=

Извлечение из кучи минимума(O(log N))Для извлечения из кучи минимума(это корневая вершина) сначала найдем нужное дерево,а затем разложим

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

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

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

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

Слайд 11Литература
1.C.A. Crane.   Linear lists and priority queues as balanced

binary trees. — Computer Science Dept, Stanford Univ. (1972).
2.Tadao Takaoka.

  Theory of 2-3 Heaps. — Cocoon (1999).
3.Кормен Т., Лейзерсон Ч., Ривест Р.  Алгоритмы: построение и анализ. — М.: МЦНМО, 2001. — С. 376-409.

Литература1.C.A. Crane.   Linear lists and priority queues as balanced binary trees. — Computer Science Dept, Stanford Univ.

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика