Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

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

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

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

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

Презентация на тему Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка

Содержание

Стек: изменение размера массиваПроблема. От клиента требуется указывать размер стекаКак увеличивать и уменьшать размер массива?Первый подходpush(): увеличивать размер массива s[] на 1pop(): уменьшать размер массива s[] на 1СтоимостьТребуется копировать все элементы в новый массивСложность вставки первых
Изменение размера массива Стек: изменение размера массиваПроблема. От клиента требуется указывать размер стекаКак увеличивать и Стек: изменение размера массиваЕсли массив полон, то создать новый массив в два Стек: амортизированная стоимость добавления в стекСтоимость добавления первых N элементов: N + Стек: изменение размера массиваКак изменять размер массива?Первый подходpush(): увеличивать размер массива s[] Стек: изменение размера массиваЭффективный подходpush(): увеличивать размер массива s[] в два раза, Стек: изменение размера массива Стек: амортизированный анализПредположение. Начиная с пустого стека, последовательность из M push/pop операций занимает время пропорциональное M Стек: использование памятиПредположение. Используется от ~ 8N до ~ 32N байт для Очередь с приоритетом(Priority Queue) Очередь с приоритетомКоллекции. Вставка и удаление элементов. Какой элемент удалять?Стек. LIFOОчередь. FIFOРандомизированная API очереди с приоритетомТребование. Элементы должны быть сравнимы Использование очереди с приоритетам Пример очереди с приоритетомЗадача. Найти наибольшие М элементов в потоке из N Пример очереди с приоритетомЗадача. Найти наибольшие М элементов в потоке из N Пример очереди с приоритетомЗадача. Найти наибольшие М элементов в потоке из N элементов Очередь с приоритетом: неупорядоченная и упорядоченная реализация Очередь с приоритетом: неупорядоченная реализация Пример очереди с приоритетомЗадача. Все операции эффективны Бинарная пирамида(Binary Heaps) Полное бинарное деревоБинарное дерево. Пустота или узел с левым и правым бинарным Полное бинарное дерево Бинарная пирамидаБинарная пирамида. Пирамидально упорядоченное полное бинарное дерево можно представить в виде Бинарная пирамидаСамый большой ключ находится в корне по адресу а[1]Пользуйтесь индексами для Продвижение в пирамидеЕсли дочерний узел больше родительскогоПоменять местами дочерний и родительский узелПовторять Вставка в пирамидеВставка. Добавить узел в конец и поднимать его вышеСтоимость. Не более 1+log2N сравнений Спуск в пирамидеЕсли родительский узел меньше одного (или двух) дочернихПоменять местами родительский Удалить максимальный узел в пирамидеУдаление максимального узла. Поменять корень с последним узлом Бинарная пирамидаВставка. Добавить узел в конец и поднимать его вышеУдаление максимального узла. Бинарная пирамида: реализация на Java Реализация очереди с приоритетом Пирамидальная сортировка(Heapsort) Пирамидальная сортировкаСоздать пирамиду из всех N ключейПовторять удаление максимального ключа Пирамидальная сортировка Пирамидальная сортировкаКонструктор пирамиды. Создать max пирамиду восходящим методомВидео 2Видео 3 Пирамидальная сортировка: конструкторПервый проход. Создать пирамиду используя восходящий метод Пирамидальная сортировкаВторой проходУдалять максимум поочередноВосстановить порядок в пирамиде Пирамидальная сортировка: реализация на Java Пирамидальная сортировка Пирамидальная сортировка Пирамидальная сортировка: математический анализПервый проход Алгоритмы сортировки
Слайды презентации

Слайд 2 Стек: изменение размера массива
Проблема. От клиента требуется указывать

Стек: изменение размера массиваПроблема. От клиента требуется указывать размер стекаКак увеличивать

размер стека
Как увеличивать и уменьшать размер массива?

Первый подход
push(): увеличивать

размер массива s[] на 1
pop(): уменьшать размер массива s[] на 1

Стоимость
Требуется копировать все элементы в новый массив
Сложность вставки первых N элементов 1+2+3+...+N ~ N2/2

Слайд 3 Стек: изменение размера массива
Если массив полон, то создать

Стек: изменение размера массиваЕсли массив полон, то создать новый массив в

новый массив в два раза больше и копировать элементы
Стоимость.

Сложность вставки первых N элементов пропорциональна N

Слайд 4 Стек: амортизированная стоимость добавления в стек
Стоимость добавления первых

Стек: амортизированная стоимость добавления в стекСтоимость добавления первых N элементов: N

N элементов: N + (2 + 4 + 8

+ … + N) ~ 3N

Слайд 5 Стек: изменение размера массива
Как изменять размер массива?
Первый подход
push():

Стек: изменение размера массиваКак изменять размер массива?Первый подходpush(): увеличивать размер массива

увеличивать размер массива s[] в два раза, когда массив

полон
pop(): уменьшать размер массива s[] в два раза, когда массив на половину пуст
Худший случай дорог
Представим push-pop-push-pop-..., когда массив полон
Сложность каждой операции пропорциональна N

Слайд 6 Стек: изменение размера массива
Эффективный подход
push(): увеличивать размер массива

Стек: изменение размера массиваЭффективный подходpush(): увеличивать размер массива s[] в два

s[] в два раза, когда массив полон
pop(): уменьшать размер

массива s[] в два раза, когда массив заполнен на четверть

Массив заполнен от 25% до 100%

Слайд 7 Стек: изменение размера массива

Стек: изменение размера массива

Слайд 8 Стек: амортизированный анализ
Предположение. Начиная с пустого стека, последовательность

Стек: амортизированный анализПредположение. Начиная с пустого стека, последовательность из M push/pop операций занимает время пропорциональное M

из M push/pop операций занимает время пропорциональное M

Слайд 9 Стек: использование памяти
Предположение. Используется от ~ 8N до

Стек: использование памятиПредположение. Используется от ~ 8N до ~ 32N байт

~ 32N байт для стека из N элементов
~ 8N

когда стек полон
~ 32N когда стек заполнен на четверть

Учитывается память, занимаемая самим стеком, но не данными

Слайд 10 Очередь с приоритетом
(Priority Queue)

Очередь с приоритетом(Priority Queue)

Слайд 11 Очередь с приоритетом
Коллекции. Вставка и удаление элементов. Какой

Очередь с приоритетомКоллекции. Вставка и удаление элементов. Какой элемент удалять?Стек. LIFOОчередь.

элемент удалять?
Стек. LIFO
Очередь. FIFO
Рандомизированная очередь. Удаляется случайный элемент
Очередь с

приоритетом. Удаляется самый большой (или маленький) элемент

Слайд 12 API очереди с приоритетом
Требование. Элементы должны быть сравнимы

API очереди с приоритетомТребование. Элементы должны быть сравнимы

Слайд 13 Использование очереди с приоритетам

Использование очереди с приоритетам

Слайд 14 Пример очереди с приоритетом
Задача. Найти наибольшие М элементов

Пример очереди с приоритетомЗадача. Найти наибольшие М элементов в потоке из

в потоке из N элементов
Отслеживание транзакций
Поиск файлов и директорий
Ограничение.

Не хватает памяти для хранения N элементов

Слайд 15 Пример очереди с приоритетом
Задача. Найти наибольшие М элементов

Пример очереди с приоритетомЗадача. Найти наибольшие М элементов в потоке из

в потоке из N элементов
Отслеживание транзакций
Поиск файлов и директорий
Ограничение.

Не хватает памяти для хранения N элементов

Слайд 16 Пример очереди с приоритетом
Задача. Найти наибольшие М элементов

Пример очереди с приоритетомЗадача. Найти наибольшие М элементов в потоке из N элементов

в потоке из N элементов

Слайд 17 Очередь с приоритетом: неупорядоченная и упорядоченная реализация

Очередь с приоритетом: неупорядоченная и упорядоченная реализация

Слайд 18 Очередь с приоритетом: неупорядоченная реализация

Очередь с приоритетом: неупорядоченная реализация

Слайд 19 Пример очереди с приоритетом
Задача. Все операции эффективны

Пример очереди с приоритетомЗадача. Все операции эффективны

Слайд 20 Бинарная пирамида
(Binary Heaps)

Бинарная пирамида(Binary Heaps)

Слайд 21 Полное бинарное дерево
Бинарное дерево. Пустота или узел с

Полное бинарное деревоБинарное дерево. Пустота или узел с левым и правым

левым и правым бинарным поддеревом
Полное дерево. Полностью сбалансированное, за

исключением последнего уровня

Свойство. Высота полного дерева из N-1 узлов равна
Высота возрастает когда N равно степени двойки

Слайд 22 Полное бинарное дерево

Полное бинарное дерево

Слайд 23 Бинарная пирамида
Бинарная пирамида. Пирамидально упорядоченное полное бинарное дерево

Бинарная пирамидаБинарная пирамида. Пирамидально упорядоченное полное бинарное дерево можно представить в

можно представить в виде массива
Пирамидально упорядоченное бинарное дерево
Ключи в

узлах
Ключ родительского узла не меньше чем дочернего
Представление в массиве
Индексы начинаются с 1
Узлы упорядочены по уровням
Явные связи не нужны

Слайд 24 Бинарная пирамида
Самый большой ключ находится в корне по

Бинарная пирамидаСамый большой ключ находится в корне по адресу а[1]Пользуйтесь индексами

адресу а[1]
Пользуйтесь индексами для перемещения по массиву
Родитель узла k

находится в k/2
Потомки узла k находятся в 2k и 2k+1

Слайд 25 Продвижение в пирамиде
Если дочерний узел больше родительского
Поменять местами

Продвижение в пирамидеЕсли дочерний узел больше родительскогоПоменять местами дочерний и родительский

дочерний и родительский узел
Повторять до тех пор пока не

будет восстановлена пирамидальная упорядоченность

Принцип Питера. Узел продвигается до уровня своей некомпетентности

Слайд 26 Вставка в пирамиде
Вставка. Добавить узел в конец и

Вставка в пирамидеВставка. Добавить узел в конец и поднимать его вышеСтоимость. Не более 1+log2N сравнений

поднимать его выше
Стоимость. Не более 1+log2N сравнений

Слайд 27 Спуск в пирамиде
Если родительский узел меньше одного (или

Спуск в пирамидеЕсли родительский узел меньше одного (или двух) дочернихПоменять местами

двух) дочерних
Поменять местами родительский и больший дочерний узел
Повторять до

тех пор пока не будет восстановлена пирамидальная упорядоченность

Слайд 28 Удалить максимальный узел в пирамиде
Удаление максимального узла. Поменять

Удалить максимальный узел в пирамидеУдаление максимального узла. Поменять корень с последним

корень с последним узлом и спустить его ниже
Стоимость. Не

более 2log2N сравнений

Слайд 29 Бинарная пирамида
Вставка. Добавить узел в конец и поднимать

Бинарная пирамидаВставка. Добавить узел в конец и поднимать его вышеУдаление максимального

его выше
Удаление максимального узла. Поменять корень с последним узлом

и спустить его ниже
Видео 1

Слайд 30 Бинарная пирамида: реализация на Java

Бинарная пирамида: реализация на Java

Слайд 31 Реализация очереди с приоритетом

Реализация очереди с приоритетом

Слайд 32

Слайд 33

Слайд 34 Пирамидальная сортировка
(Heapsort)

Пирамидальная сортировка(Heapsort)

Слайд 35 Пирамидальная сортировка
Создать пирамиду из всех N ключей
Повторять удаление

Пирамидальная сортировкаСоздать пирамиду из всех N ключейПовторять удаление максимального ключа

максимального ключа

Слайд 36 Пирамидальная сортировка

Пирамидальная сортировка

Слайд 37 Пирамидальная сортировка
Конструктор пирамиды. Создать max пирамиду восходящим методом
Видео

Пирамидальная сортировкаКонструктор пирамиды. Создать max пирамиду восходящим методомВидео 2Видео 3

2
Видео 3

Слайд 38 Пирамидальная сортировка: конструктор
Первый проход. Создать пирамиду используя восходящий

Пирамидальная сортировка: конструкторПервый проход. Создать пирамиду используя восходящий метод

метод

Слайд 39

Слайд 40 Пирамидальная сортировка
Второй проход
Удалять максимум поочередно
Восстановить порядок в пирамиде

Пирамидальная сортировкаВторой проходУдалять максимум поочередноВосстановить порядок в пирамиде

Слайд 41

Слайд 42 Пирамидальная сортировка: реализация на Java

Пирамидальная сортировка: реализация на Java

Слайд 43 Пирамидальная сортировка

Пирамидальная сортировка

Слайд 44 Пирамидальная сортировка

Пирамидальная сортировка

Слайд 45 Пирамидальная сортировка: математический анализ
Первый проход

Пирамидальная сортировка: математический анализПервый проход

и перестановок
Второй проход

Алгоритм, не требующий дополнительной памяти и работающий за NlogN в худшем случае
Быстрая сортировка
Сортировка слиянием
Нижняя граница. Пирамидальная сортировка оптимальна по памяти и по времени
Внутренний цикл длиннее, чем у Q-sort
Плохо кэшируется
Не устойчива
  • Имя файла: izmenenie-razmera-massiva-ochered-s-prioritetom-binarnaya-piramida-piramidalnaya-sortirovka.pptx
  • Количество просмотров: 112
  • Количество скачиваний: 0
- Предыдущая Как изучали мир
Следующая - Феномен Артюса

Похожие презентации

животные животные 92
Компьютерные сети Компьютерные сети 103
Логические функции Логические функции 126
Операторы модификации данных Операторы модификации данных 127
Графический редактор Графический редактор 138
4. Java OOP. 5. Abstract Classes 4. Java OOP. 5. Abstract Classes 152
dom-ui dom-ui 239
Презентация по информатике на тему Алгебра логики Презентация по информатике на тему Алгебра логики 157
Диалоговые панели Диалоговые панели 176
Архитектура системной платы современных компьютеров Архитектура системной платы современных компьютеров 130
Логический подход к построению систем ИИ Логический подход к построению систем ИИ 130
Кроссворд - проверь свои знания Кроссворд - проверь свои знания 182
Медицинские информационные системы уровня структурного подразделения медицинского учреждения. Информационные системы службы питания. Примеры некоторых информационных систем служб питания. Подсистема автоматизации службы питания Интерин PROMIS Медицинские информационные системы уровня структурного подразделения медицинского учреждения. Информационные системы службы питания. Примеры некоторых информационных систем служб питания. Подсистема автоматизации службы питания Интерин PROMIS 252
Настройка безопасности сети с помощью IPSec Настройка безопасности сети с помощью IPSec 149
MSC.Dytran - 07 MSC.Dytran - 07 125
“Интернет желісі” “Электронды поштамен жұмыс істеу принципі” “Интернет желісі” “Электронды поштамен жұмыс істеу принципі” 212
Основы предварительного информирования Основы предварительного информирования 142
Windows XP. Работа с окнами, объектами и др. Windows XP. Работа с окнами, объектами и др. 143
Плоттеры Плоттеры 198
Методы и средства защиты компьютерной информации Методы и средства защиты компьютерной информации 107
Физическая защита данных на дисках Физическая защита данных на дисках 132
Контрольная работа по информатике №4, 4 класс Контрольная работа по информатике №4, 4 класс 105
UML. Диаграмма Sequence UML. Диаграмма Sequence 193
Мультимедиа. Аналоговый и цифровой звук. Технические средства мультимедиа Мультимедиа. Аналоговый и цифровой звук. Технические средства мультимедиа 121
Виды информационных технологий Виды информационных технологий 140
Информация и информационные процессы в неживой и живой природе Информация и информационные процессы в неживой и живой природе 272
История средств вычислительной техники История средств вычислительной техники 202
Классификация и архитектура информационно-вычислительных сетей Классификация и архитектура информационно-вычислительных сетей 193
Урок по информатике для 2 класса Виды информации по способу восприятия Урок по информатике для 2 класса Виды информации по способу восприятия 199
Локальні та глобальні мережі Локальні та глобальні мережі 124