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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №1Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №2Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №3Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №4Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №5Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №6Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №7Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №8Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №9Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №10Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №11Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №12Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №13Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №14Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №15Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №16Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №17Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №18Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №19Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №20Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №21Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №22Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №23Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №24Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №25Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №26Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №27Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №28Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №29Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №30Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №31Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №32Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №33Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №34Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №35Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №36Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №37Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №38Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №39Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №40Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №41Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №42Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №43Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №44Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №45Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №46
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка. Доклад-сообщение содержит 46 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Изменение размера массива
Описание слайда:
Изменение размера массива

Слайд 2


Стек: изменение размера массива Проблема. От клиента требуется указывать размер стека Как увеличивать и уменьшать размер массива? Первый подход push(): увеличивать размер массива s[] на 1 pop(): уменьшать размер массива s[] на 1 Стоимость Требуется копировать все элементы в новый массив Сложность вставки первых N элементов 1+2+3+...+N ~ N2/2
Описание слайда:
Стек: изменение размера массива Проблема. От клиента требуется указывать размер стека Как увеличивать и уменьшать размер массива? Первый подход push(): увеличивать размер массива s[] на 1 pop(): уменьшать размер массива s[] на 1 Стоимость Требуется копировать все элементы в новый массив Сложность вставки первых N элементов 1+2+3+...+N ~ N2/2

Слайд 3


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

Слайд 4


Стек: амортизированная стоимость добавления в стек Стоимость добавления первых N элементов: N + (2 + 4 + 8 + … + N) ~ 3N
Описание слайда:
Стек: амортизированная стоимость добавления в стек Стоимость добавления первых N элементов: N + (2 + 4 + 8 + … + N) ~ 3N

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


Бинарная пирамида (Binary Heaps)
Описание слайда:
Бинарная пирамида (Binary Heaps)

Слайд 21


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

Слайд 22


Полное бинарное дерево
Описание слайда:
Полное бинарное дерево

Слайд 23


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

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


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

Слайд 28


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

Слайд 29


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

Слайд 30


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

Слайд 31


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

Слайд 32


Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №32
Описание слайда:

Слайд 33


Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №33
Описание слайда:

Слайд 34


Пирамидальная сортировка (Heapsort)
Описание слайда:
Пирамидальная сортировка (Heapsort)

Слайд 35


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

Слайд 36


Пирамидальная сортировка
Описание слайда:
Пирамидальная сортировка

Слайд 37


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

Слайд 38


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

Слайд 39


Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №39
Описание слайда:

Слайд 40


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

Слайд 41


Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №41
Описание слайда:

Слайд 42


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

Слайд 43


Пирамидальная сортировка
Описание слайда:
Пирамидальная сортировка

Слайд 44


Пирамидальная сортировка
Описание слайда:
Пирамидальная сортировка

Слайд 45


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

Слайд 46


Алгоритмы сортировки
Описание слайда:
Алгоритмы сортировки

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию