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

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

Лекция № 15. Поиск и индексация Лекция № 15. Поиск и индексация 116
Үзілістерді ұйымдастыру принціптері.Үзілістін көпдеңгейлік жүйелері. Артықшылықтары Үзілістерді ұйымдастыру принціптері.Үзілістін көпдеңгейлік жүйелері. Артықшылықтары 107
Презентация по информатике на тему Поисковые информационные системы 9 класс Презентация по информатике на тему Поисковые информационные системы 9 класс 163
Variables Variables 141
Алгоритм и его формальное исполнение. Алгоритм и его формальное исполнение. 121
Презентация Урок 8-4 Информация и информационные процессы в технике (8 класс, Угринович Н.Д.) Презентация Урок 8-4 Информация и информационные процессы в технике (8 класс, Угринович Н.Д.) 155
Презентация по информатике Алгоритмика Презентация по информатике Алгоритмика 142
Растровая графика Растровая графика 98
работотехника работотехника 191
Массивы Массивы 169
Клавиатура компьютера Клавиатура компьютера 125
Задачи на дроби Задачи на дроби 133
Информационная система по учету объектов и источников негативного воздействия на окружающую среду Информационная система по учету объектов и источников негативного воздействия на окружающую среду 91
Работа с текстом в HTML Работа с текстом в HTML 120
Второе поколение ЭВМ Второе поколение ЭВМ 109
Задача о минимальном разрезе на взвешенном бисвязном графе Задача о минимальном разрезе на взвешенном бисвязном графе 124
Графический редактор Adobe Photoshop Графический редактор Adobe Photoshop 98
Электронная цифровая подпись (ЭЦП) Электронная цифровая подпись (ЭЦП) 115
Разработка мобильного приложения для ГКУ Центр социальной защиты населения по Кумылженскому району Разработка мобильного приложения для ГКУ Центр социальной защиты населения по Кумылженскому району 115
Двоичная система счисления Двоичная система счисления 106
Программное обеспечение компьютера 7 класс. Программное обеспечение компьютера 7 класс. 173
Компьютерные вирусы Компьютерные вирусы 140
Безопасный интернет Безопасный интернет 107
Алгоритмизация и требования к алгоритму Алгоритмизация и требования к алгоритму 115
Представлення Представлення 131
Расчет контрольного числа кода Расчет контрольного числа кода 138
Презентация Алгоритм работы с Google Формами Презентация Алгоритм работы с Google Формами 160
Преобразование двумерных массивов Преобразование двумерных массивов 121
Форматирование вывода данных (некоторые манипуляторы потокового ввода/вывода) Форматирование вывода данных (некоторые манипуляторы потокового ввода/вывода) 98
Самоорганизация в сети Веб Самоорганизация в сети Веб 143