Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
36 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
335.16 kB
Просмотров:
63
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Двоичная куча](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img0.jpg)
Содержание слайда: Двоичная куча
№2 слайд![Двоичная куча пирамида binary](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img1.jpg)
Содержание слайда: Двоичная куча – пирамида (binary heap)
№3 слайд![История появления Бинарная](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img2.jpg)
Содержание слайда: История появления
Бинарная куча была Джоном Уильямом Джозефом Уильямсом в 1964 году как структура данных для heapsort(пирамидальной сортровки).
Но наибольшего применения достигла лишь в 1990-х годах, в эпоху повсеместного использования компьютеров. В том числе двоичную кучу существенно популяризировал Чарльз Лейзерсон, который также использовал её в разработке собственного языка программирования Clik.
№4 слайд![Двоичная куча Приоритет в](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img3.jpg)
Содержание слайда: Двоичная куча
Приоритет в любой вершине не меньше, чем приоритет её потомков
Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
Последний слой заполняется слева направо без «дырок».
№5 слайд![Бинарная куча пирамида binary](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img4.jpg)
Содержание слайда: Бинарная куча – пирамида (binary heap)
№6 слайд![Реализация бинарной кучи на](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img5.jpg)
Содержание слайда: Реализация бинарной кучи на основе массива
№7 слайд![Реализация бинарной кучи на](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img6.jpg)
Содержание слайда: Реализация бинарной кучи на основе массива
№8 слайд![Поиск максимального элемента](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img7.jpg)
Содержание слайда: Поиск максимального элемента
№9 слайд![Вставка элемента в бинарную](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img8.jpg)
Содержание слайда: Вставка элемента в бинарную кучу
№10 слайд![Вставка элемента в бинарную](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img9.jpg)
Содержание слайда: Вставка элемента в бинарную кучу
№11 слайд![Поиск максимального элемента](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img10.jpg)
Содержание слайда: Поиск максимального элемента
№12 слайд![Удаление максимального](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img11.jpg)
Содержание слайда: Удаление максимального элемента
№13 слайд![Удаление максимального](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img12.jpg)
Содержание слайда: Удаление максимального элемента
№14 слайд![Удаление максимального](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img13.jpg)
Содержание слайда: Удаление максимального элемента
№15 слайд![Создание пустой кучи](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img14.jpg)
Содержание слайда: Создание пустой кучи
№16 слайд![Удаление кучи](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img15.jpg)
Содержание слайда: Удаление кучи
№17 слайд![Восстановление свойств кучи](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img16.jpg)
Содержание слайда: Восстановление свойств кучи (max-heap)
№18 слайд![Работа с бинарной кучей](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img17.jpg)
Содержание слайда: Работа с бинарной кучей
№19 слайд![Изменение кучи](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img18.jpg)
Содержание слайда: Изменение кучи
№20 слайд![Увеличение ключа](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img19.jpg)
Содержание слайда: Увеличение ключа
№21 слайд![Построение бинарной кучи](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img20.jpg)
Содержание слайда: Построение бинарной кучи
№22 слайд![Построение бинарной кучи v](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img21.jpg)
Содержание слайда: Построение бинарной кучи (v1)
№23 слайд![Построение бинарной кучи v](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img22.jpg)
Содержание слайда: Построение бинарной кучи (v2)
№24 слайд![Использование двоичной кучи](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img23.jpg)
Содержание слайда: Использование двоичной кучи
№25 слайд![Очередь с приоритетом](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img24.jpg)
Содержание слайда: Очередь с приоритетом (priority queue)
№26 слайд![Сравнение оценки алгоритмов](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img25.jpg)
Содержание слайда: Сравнение оценки алгоритмов
№27 слайд![Алгоритм Дейкстры Обозначим](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img26.jpg)
Содержание слайда: Алгоритм Дейкстры
Обозначим через n количество вершин, а через m — количество рёбер в графе G.
В обычном простейшем случае получаем O(n*n).
С помощью двоичной кучи сложность алгоритма получается:
О(log n * (n + m)).
Так как время удаления вершины из станет log n при том, что время модификации тоже возрастёт до log n. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, О(log n * (n + m)).
№28 слайд![Сортировка на базе бинарной](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img27.jpg)
Содержание слайда: Сортировка на базе бинарной кучи
№29 слайд![Сортировка на базе бинарной](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img28.jpg)
Содержание слайда: Сортировка на базе бинарной кучи
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 слайд![Сортировка на базе бинарной](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img29.jpg)
Содержание слайда: Сортировка на базе бинарной кучи
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
№31 слайд![Оценки работы алгоритма](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img30.jpg)
Содержание слайда: Оценки работы алгоритма
№32 слайд![Скорость работы программы](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img31.jpg)
Содержание слайда: Скорость работы программы
№33 слайд![Скорость работы программы с](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img32.jpg)
Содержание слайда: Скорость работы программы с выводом данных
№34 слайд![Отношение](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img33.jpg)
Содержание слайда: Отношение
№35 слайд![Отношение теоретического к](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img34.jpg)
Содержание слайда: Отношение теоретического к практическому
№36 слайд![Спасибо за внимание!](/documents_6/169e6773044345b8afe79a33a2dbe2fa/img35.jpg)
Содержание слайда: Спасибо за внимание!