Презентация Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка абсолютно бесплатно. Урок-презентация на эту тему содержит всего 46 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:46 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:3.44 MB
- Просмотров:62
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Изменение размера массива
№2 слайд
Содержание слайда: Стек: изменение размера массива
Проблема. От клиента требуется указывать размер стека
Как увеличивать и уменьшать размер массива?
Первый подход
push(): увеличивать размер массива s[] на 1
pop(): уменьшать размер массива s[] на 1
Стоимость
Требуется копировать все элементы в новый массив
Сложность вставки первых N элементов 1+2+3+...+N ~ N2/2
№3 слайд
Содержание слайда: Стек: изменение размера массива
Если массив полон, то создать новый массив в два раза больше и копировать элементы
№4 слайд
Содержание слайда: Стек: амортизированная стоимость добавления в стек
Стоимость добавления первых N элементов: N + (2 + 4 + 8 + … + N) ~ 3N
№5 слайд
Содержание слайда: Стек: изменение размера массива
Как изменять размер массива?
Первый подход
push(): увеличивать размер массива s[] в два раза, когда массив полон
pop(): уменьшать размер массива s[] в два раза, когда массив на половину пуст
Худший случай дорог
Представим push-pop-push-pop-..., когда массив полон
Сложность каждой операции пропорциональна N
№6 слайд
Содержание слайда: Стек: изменение размера массива
Эффективный подход
push(): увеличивать размер массива s[] в два раза, когда массив полон
pop(): уменьшать размер массива s[] в два раза, когда массив заполнен на четверть
№7 слайд
Содержание слайда: Стек: изменение размера массива
№8 слайд
Содержание слайда: Стек: амортизированный анализ
Предположение. Начиная с пустого стека, последовательность из M push/pop операций занимает время пропорциональное M
№9 слайд
Содержание слайда: Стек: использование памяти
Предположение. Используется от ~ 8N до ~ 32N байт для стека из N элементов
~ 8N когда стек полон
~ 32N когда стек заполнен на четверть
№10 слайд
Содержание слайда: Очередь с приоритетом
(Priority Queue)
№11 слайд
Содержание слайда: Очередь с приоритетом
Коллекции. Вставка и удаление элементов. Какой элемент удалять?
Стек. LIFO
Очередь. FIFO
Рандомизированная очередь. Удаляется случайный элемент
Очередь с приоритетом. Удаляется самый большой (или маленький) элемент
№12 слайд
Содержание слайда: API очереди с приоритетом
Требование. Элементы должны быть сравнимы
№13 слайд
Содержание слайда: Использование очереди с приоритетам
№14 слайд
Содержание слайда: Пример очереди с приоритетом
Задача. Найти наибольшие М элементов в потоке из N элементов
Отслеживание транзакций
Поиск файлов и директорий
Ограничение. Не хватает памяти для хранения N элементов
№15 слайд
Содержание слайда: Пример очереди с приоритетом
Задача. Найти наибольшие М элементов в потоке из N элементов
Отслеживание транзакций
Поиск файлов и директорий
Ограничение. Не хватает памяти для хранения N элементов
№16 слайд
Содержание слайда: Пример очереди с приоритетом
Задача. Найти наибольшие М элементов в потоке из N элементов
№17 слайд
Содержание слайда: Очередь с приоритетом: неупорядоченная и упорядоченная реализация
№18 слайд
Содержание слайда: Очередь с приоритетом: неупорядоченная реализация
№19 слайд
Содержание слайда: Пример очереди с приоритетом
Задача. Все операции эффективны
№20 слайд
Содержание слайда: Бинарная пирамида
(Binary Heaps)
№21 слайд
Содержание слайда: Полное бинарное дерево
Бинарное дерево. Пустота или узел с левым и правым бинарным поддеревом
Полное дерево. Полностью сбалансированное, за исключением последнего уровня
№22 слайд
Содержание слайда: Полное бинарное дерево
№23 слайд
Содержание слайда: Бинарная пирамида
Бинарная пирамида. Пирамидально упорядоченное полное бинарное дерево можно представить в виде массива
№24 слайд
Содержание слайда: Бинарная пирамида
Самый большой ключ находится в корне по адресу а[1]
№25 слайд
Содержание слайда: Продвижение в пирамиде
Если дочерний узел больше родительского
Поменять местами дочерний и родительский узел
Повторять до тех пор пока не будет восстановлена пирамидальная упорядоченность
№26 слайд
Содержание слайда: Вставка в пирамиде
Вставка. Добавить узел в конец и поднимать его выше
Стоимость. Не более 1+log2N сравнений
№27 слайд
Содержание слайда: Спуск в пирамиде
Если родительский узел меньше одного (или двух) дочерних
Поменять местами родительский и больший дочерний узел
Повторять до тех пор пока не будет восстановлена пирамидальная упорядоченность
№28 слайд
Содержание слайда: Удалить максимальный узел в пирамиде
Удаление максимального узла. Поменять корень с последним узлом и спустить его ниже
Стоимость. Не более 2log2N сравнений
№29 слайд
Содержание слайда: Бинарная пирамида
Вставка. Добавить узел в конец и поднимать его выше
Удаление максимального узла. Поменять корень с последним узлом и спустить его ниже
Видео 1
№30 слайд
Содержание слайда: Бинарная пирамида: реализация на Java
№31 слайд
Содержание слайда: Реализация очереди с приоритетом
№32 слайд
Содержание слайда:
№33 слайд
Содержание слайда:
№34 слайд
Содержание слайда: Пирамидальная сортировка
(Heapsort)
№35 слайд
Содержание слайда: Пирамидальная сортировка
Создать пирамиду из всех N ключей
Повторять удаление максимального ключа
№36 слайд
Содержание слайда: Пирамидальная сортировка
№37 слайд
Содержание слайда: Пирамидальная сортировка
Конструктор пирамиды. Создать max пирамиду восходящим методом
Видео 2
Видео 3
№38 слайд
Содержание слайда: Пирамидальная сортировка: конструктор
Первый проход. Создать пирамиду используя восходящий метод
№39 слайд
Содержание слайда:
№40 слайд
Содержание слайда: Пирамидальная сортировка
Второй проход
Удалять максимум поочередно
Восстановить порядок в пирамиде
№41 слайд
Содержание слайда:
№42 слайд
Содержание слайда: Пирамидальная сортировка: реализация на Java
№43 слайд
Содержание слайда: Пирамидальная сортировка
№44 слайд
Содержание слайда: Пирамидальная сортировка
№45 слайд
Содержание слайда: Пирамидальная сортировка: математический анализ
Первый проход <= 2N сравнений и перестановок
Второй проход <= 2N log2N сравнений и перестановок
Значение. Алгоритм, не требующий дополнительной памяти и работающий за NlogN в худшем случае
Быстрая сортировка
Сортировка слиянием
Нижняя граница. Пирамидальная сортировка оптимальна по памяти и по времени
Внутренний цикл длиннее, чем у Q-sort
Плохо кэшируется
Не устойчива
№46 слайд
Содержание слайда: Алгоритмы сортировки
Скачать все slide презентации Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка одним архивом:
