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

Содержание

Стек: изменение размера массива Проблема. От клиента требуется указывать размер стека Как увеличивать и уменьшать размер массива? Первый подход push(): увеличивать размер массива s[] на 1 pop(): уменьшать размер

Слайд 1Изменение размера массива

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

и уменьшать размер массива?

Первый подход
push(): увеличивать размер массива s[] на 1
pop(): уменьшать размер массива s[] на 1

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

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

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

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

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

+ (2 + 4 + 8 + … + N) ~ 3N

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

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

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

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

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

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

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

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

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

для стека из N элементов
~ 8N когда стек полон
~ 32N когда стек заполнен на четверть

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

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

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

FIFO
Рандомизированная очередь. Удаляется случайный элемент
Очередь с приоритетом. Удаляется самый большой (или маленький) элемент

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

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

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

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

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

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

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

N элементов

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

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

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

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

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

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

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

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

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

виде массива

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

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

для перемещения по массиву
Родитель узла k находится в k/2
Потомки узла k находятся в 2k и 2k+1

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

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

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

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

Не более 1+log2N сравнений

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

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

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

узлом и спустить его ниже
Стоимость. Не более 2log2N сравнений

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

узла. Поменять корень с последним узлом и спустить его ниже
Видео 1

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

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

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

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

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

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

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

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

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

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

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

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

<= 2N log2N сравнений и перестановок
Значение. Алгоритм, не требующий дополнительной памяти и работающий за NlogN в худшем случае
Быстрая сортировка
Сортировка слиянием
Нижняя граница. Пирамидальная сортировка оптимальна по памяти и по времени
Внутренний цикл длиннее, чем у Q-sort
Плохо кэшируется
Не устойчива

Слайд 46Алгоритмы сортировки

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

Информационное моделирование на компьютере 356
Основы логики 225
АРМ 1. Информационная подсистема 210
Стандартные паттерны 246
Качественные методы обработки данных 333
Пользовательский тип данных 243

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

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

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

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