Что такое 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
  • Количество просмотров: 108
  • Количество скачиваний: 0
- Предыдущая Как изучали мир
Следующая - Феномен Артюса

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

Einintellektuelles haus Einintellektuelles haus 95
СКУР Пассажир. Система контроля уровня риска СКУР Пассажир. Система контроля уровня риска 114
WEB application security WEB application security 114
Презентация к уроку информатики Презентация к уроку информатики 139
Функции и процедуры Функции и процедуры 108
Искусственный интеллект Искусственный интеллект 135
Сетевые образовательные сообщества Сетевые образовательные сообщества 114
Программирование под Maemo Программирование под Maemo 152
Нечеткая логика в информационных системах и технологиях Нечеткая логика в информационных системах и технологиях 146
Интерфейс передачи сообщений MPI Интерфейс передачи сообщений MPI 106
Базы данных 13 Базы данных 13 119
Информационный калейдоскоп Информационный калейдоскоп 128
Создание сайтов Создание сайтов 145
Упорядочивание и поиск (в Интернете) информации Упорядочивание и поиск (в Интернете) информации 129
Работа с битами. Команды сдвига. Логические команды. Адресное пространство. Способы адресации. Организация сравнения. Циклы Работа с битами. Команды сдвига. Логические команды. Адресное пространство. Способы адресации. Организация сравнения. Циклы 127
Редакторы HTML+CSS Редакторы HTML+CSS 133
Безопасная работа в социальных сетях Безопасная работа в социальных сетях 138
Программа ЕГЭ по информатике Программа ЕГЭ по информатике 126
Обзор возможных исполнителей в заданиях ГИА по информатике 9 класс Обзор возможных исполнителей в заданиях ГИА по информатике 9 класс 131
Логічні функції Логічні функції 115
Алгоритм построения конкурсно-игровой программы Алгоритм построения конкурсно-игровой программы 120
Возможности BIOS Возможности BIOS 128
Microsoft Office Word Microsoft Office Word 105
Информационное моделирование на компьютере Информационное моделирование на компьютере 115
Использование передовых технологий с целью сокращения сроков создания АТ Использование передовых технологий с целью сокращения сроков создания АТ 126
Сортировка и поиск. Пузырьковая сортировка Сортировка и поиск. Пузырьковая сортировка 169
Социальные сети Социальные сети 124
Алгоритм определение свойства форма записи Алгоритм определение свойства форма записи 118
Векторная графика. Рисуем солнышко Векторная графика. Рисуем солнышко 135
Компьютерная зависимость подростков Компьютерная зависимость подростков 93