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

На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Двоичная куча – пирамида (binary heap) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 36 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.

Презентации » Устройства и комплектующие » Двоичная куча – пирамида (binary heap)

Просмотр ВСЕЙ презентации! ЖМИТЕ

Оцените презентацию от 1 до 5 баллов!

Смотреть онлайн
Скачать

Тип файла:

ppt / pptx (powerpoint)
Всего слайдов:

36 слайдов
Для класса:

1,2,3,4,5,6,7,8,9,10,11
Размер файла:

335.16 kB
Просмотров:

63
Скачиваний:

0
Автор:

неизвестен

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

№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

№30 слайд