Двоичная куча – пирамида (binary heap) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Двоичная куча – пирамида (binary heap), слайд №1

Двоичная куча – пирамида (binary heap), слайд №2

Двоичная куча – пирамида (binary heap), слайд №3

Двоичная куча – пирамида (binary heap), слайд №4

Двоичная куча – пирамида (binary heap), слайд №5

Двоичная куча – пирамида (binary heap), слайд №6

Двоичная куча – пирамида (binary heap), слайд №7

Двоичная куча – пирамида (binary heap), слайд №8

Двоичная куча – пирамида (binary heap), слайд №9

Двоичная куча – пирамида (binary heap), слайд №10

Двоичная куча – пирамида (binary heap), слайд №11

Двоичная куча – пирамида (binary heap), слайд №12

Двоичная куча – пирамида (binary heap), слайд №13

Двоичная куча – пирамида (binary heap), слайд №14

Двоичная куча – пирамида (binary heap), слайд №15

Двоичная куча – пирамида (binary heap), слайд №16

Двоичная куча – пирамида (binary heap), слайд №17

Двоичная куча – пирамида (binary heap), слайд №18

Двоичная куча – пирамида (binary heap), слайд №19

Двоичная куча – пирамида (binary heap), слайд №20

Двоичная куча – пирамида (binary heap), слайд №21

Двоичная куча – пирамида (binary heap), слайд №22

Двоичная куча – пирамида (binary heap), слайд №23

Двоичная куча – пирамида (binary heap), слайд №24

Двоичная куча – пирамида (binary heap), слайд №25

Двоичная куча – пирамида (binary heap), слайд №26

Двоичная куча – пирамида (binary heap), слайд №27

Двоичная куча – пирамида (binary heap), слайд №28

Двоичная куча – пирамида (binary heap), слайд №29

Двоичная куча – пирамида (binary heap), слайд №30

Двоичная куча – пирамида (binary heap), слайд №31

Двоичная куча – пирамида (binary heap), слайд №32

Двоичная куча – пирамида (binary heap), слайд №33

Двоичная куча – пирамида (binary heap), слайд №34

Двоичная куча – пирамида (binary heap), слайд №35

Двоичная куча – пирамида (binary heap), слайд №36

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Двоичная куча – пирамида (binary heap). Доклад-сообщение содержит 36 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

Двоичная куча

Слайд 2

Описание слайда:

Двоичная куча – пирамида (binary heap)

Слайд 3

Описание слайда:

История появления Бинарная куча была Джоном Уильямом Джозефом Уильямсом в 1964 году как структура данных для heapsort(пирамидальной сортровки). Но наибольшего применения достигла лишь в 1990-х годах, в эпоху повсеместного использования компьютеров. В том числе двоичную кучу существенно популяризировал Чарльз Лейзерсон, который также использовал её в разработке собственного языка программирования Clik.

Слайд 4

Описание слайда:

Двоичная куча Приоритет в любой вершине не меньше, чем приоритет её потомков Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой. Последний слой заполняется слева направо без «дырок».

Слайд 5

Описание слайда:

Бинарная куча – пирамида (binary heap)

Слайд 6

Описание слайда:

Реализация бинарной кучи на основе массива

Слайд 7

Описание слайда:

Реализация бинарной кучи на основе массива

Слайд 8

Описание слайда:

Поиск максимального элемента

Слайд 9

Описание слайда:

Вставка элемента в бинарную кучу

Слайд 10

Описание слайда:

Вставка элемента в бинарную кучу

Слайд 11

Описание слайда:

Поиск максимального элемента

Слайд 12

Описание слайда:

Удаление максимального элемента

Слайд 13

Описание слайда:

Удаление максимального элемента

Слайд 14

Описание слайда:

Удаление максимального элемента

Слайд 15

Описание слайда:

Создание пустой кучи

Слайд 16

Описание слайда:

Удаление кучи

Слайд 17

Описание слайда:

Восстановление свойств кучи (max-heap)

Слайд 18

Описание слайда:

Работа с бинарной кучей

Слайд 19

Описание слайда:

Изменение кучи

Слайд 20

Описание слайда:

Увеличение ключа

Слайд 21

Описание слайда:

Построение бинарной кучи

Слайд 22

Описание слайда:

Построение бинарной кучи (v1)

Слайд 23

Описание слайда:

Построение бинарной кучи (v2)

Слайд 24

Описание слайда:

Использование двоичной кучи

Слайд 25

Описание слайда:

Очередь с приоритетом (priority queue)

Слайд 26

Описание слайда:

Сравнение оценки алгоритмов

Слайд 27

Описание слайда:

Алгоритм Дейкстры Обозначим через n количество вершин, а через m — количество рёбер в графе G. В обычном простейшем случае получаем O(n*n). С помощью двоичной кучи сложность алгоритма получается: О(log n * (n + m)). Так как время удаления вершины из станет log n при том, что время модификации тоже возрастёт до log n. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, О(log n * (n + m)).

Слайд 28

Описание слайда:

Сортировка на базе бинарной кучи

Слайд 29

Описание слайда:

Сортировка на базе бинарной кучи function HeapSort(v[1:n]) h = CreateBinaryHeap(n) for i = 1 to n do HeapInsert(h, v[i], v[i]) end for for i = 1 to n do v[i] = HeapRemoveMax(h) end for end function