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

Содержание

Стек: изменение размера массива Проблема. От клиента требуется указывать размер стека Как увеличивать и уменьшать размер массива? Первый подход 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Алгоритмы сортировки

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

Лексические основы С# 387
Қолданбалы программалар пакеті 400
Форматирование информации, таблиц и ячеек 253
Содержательный подход к измерению информации 294
Симметричные криптосистемы. (Лекция 12) 427
Лекция №4. Основы работы в среде Matlab 782

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

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

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

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

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

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

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