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

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

Презентация «Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка» содержит 46 слайдов и доступна в формате ppt. Размер файла: 3.44 MB

Вы можете предварительно ознакомиться с презентацией, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати.

Просмотреть и скачать

Pic.1
Изменение размера массива
Изменение размера массива
Pic.2
Стек: изменение размера массива Проблема. От клиента требуется указывать размер стека Как увеличиват
Стек: изменение размера массива Проблема. От клиента требуется указывать размер стека Как увеличивать и уменьшать размер массива? Первый подход push(): увеличивать размер массива s[] на 1 pop(): …
Pic.3
Стек: изменение размера массива Если массив полон, то создать новый массив в два раза больше и копир
Стек: изменение размера массива Если массив полон, то создать новый массив в два раза больше и копировать элементы
Pic.4
Стек: амортизированная стоимость добавления в стек Стоимость добавления первых N элементов: N + (2 +
Стек: амортизированная стоимость добавления в стек Стоимость добавления первых N элементов: N + (2 + 4 + 8 + … + N) ~ 3N
Pic.5
Стек: изменение размера массива Как изменять размер массива? Первый подход push(): увеличивать разме
Стек: изменение размера массива Как изменять размер массива? Первый подход push(): увеличивать размер массива s[] в два раза, когда массив полон pop(): уменьшать размер массива s[] в два раза, когда …
Pic.6
Стек: изменение размера массива Эффективный подход push(): увеличивать размер массива s[] в два раза
Стек: изменение размера массива Эффективный подход push(): увеличивать размер массива s[] в два раза, когда массив полон pop(): уменьшать размер массива s[] в два раза, когда массив заполнен на …
Pic.7
Стек: изменение размера массива
Стек: изменение размера массива
Pic.8
Стек: амортизированный анализ Предположение. Начиная с пустого стека, последовательность из M push/p
Стек: амортизированный анализ Предположение. Начиная с пустого стека, последовательность из M push/pop операций занимает время пропорциональное M
Pic.9
Стек: использование памяти Предположение. Используется от ~ 8N до ~ 32N байт для стека из N элементо
Стек: использование памяти Предположение. Используется от ~ 8N до ~ 32N байт для стека из N элементов ~ 8N когда стек полон ~ 32N когда стек заполнен на четверть
Pic.10
Очередь с приоритетом (Priority Queue)
Очередь с приоритетом (Priority Queue)
Pic.11
Очередь с приоритетом Коллекции. Вставка и удаление элементов. Какой элемент удалять? Стек. LIFO Оче
Очередь с приоритетом Коллекции. Вставка и удаление элементов. Какой элемент удалять? Стек. LIFO Очередь. FIFO Рандомизированная очередь. Удаляется случайный элемент Очередь с приоритетом. Удаляется …
Pic.12
API очереди с приоритетом Требование. Элементы должны быть сравнимы
API очереди с приоритетом Требование. Элементы должны быть сравнимы
Pic.13
Использование очереди с приоритетам
Использование очереди с приоритетам
Pic.14
Пример очереди с приоритетом Задача. Найти наибольшие М элементов в потоке из N элементов Отслеживан
Пример очереди с приоритетом Задача. Найти наибольшие М элементов в потоке из N элементов Отслеживание транзакций Поиск файлов и директорий Ограничение. Не хватает памяти для хранения N элементов
Pic.15
Пример очереди с приоритетом Задача. Найти наибольшие М элементов в потоке из N элементов Отслеживан
Пример очереди с приоритетом Задача. Найти наибольшие М элементов в потоке из N элементов Отслеживание транзакций Поиск файлов и директорий Ограничение. Не хватает памяти для хранения N элементов
Pic.16
Пример очереди с приоритетом Задача. Найти наибольшие М элементов в потоке из N элементов
Пример очереди с приоритетом Задача. Найти наибольшие М элементов в потоке из N элементов
Pic.17
Очередь с приоритетом: неупорядоченная и упорядоченная реализация
Очередь с приоритетом: неупорядоченная и упорядоченная реализация
Pic.18
Очередь с приоритетом: неупорядоченная реализация
Очередь с приоритетом: неупорядоченная реализация
Pic.19
Пример очереди с приоритетом Задача. Все операции эффективны
Пример очереди с приоритетом Задача. Все операции эффективны
Pic.20
Бинарная пирамида (Binary Heaps)
Бинарная пирамида (Binary Heaps)
Pic.21
Полное бинарное дерево Бинарное дерево. Пустота или узел с левым и правым бинарным поддеревом Полное
Полное бинарное дерево Бинарное дерево. Пустота или узел с левым и правым бинарным поддеревом Полное дерево. Полностью сбалансированное, за исключением последнего уровня
Pic.22
Полное бинарное дерево
Полное бинарное дерево
Pic.23
Бинарная пирамида Бинарная пирамида. Пирамидально упорядоченное полное бинарное дерево можно предста
Бинарная пирамида Бинарная пирамида. Пирамидально упорядоченное полное бинарное дерево можно представить в виде массива
Pic.24
Бинарная пирамида Самый большой ключ находится в корне по адресу а[1]
Бинарная пирамида Самый большой ключ находится в корне по адресу а[1]
Pic.25
Продвижение в пирамиде Если дочерний узел больше родительского Поменять местами дочерний и родительс
Продвижение в пирамиде Если дочерний узел больше родительского Поменять местами дочерний и родительский узел Повторять до тех пор пока не будет восстановлена пирамидальная упорядоченность
Pic.26
Вставка в пирамиде Вставка. Добавить узел в конец и поднимать его выше Стоимость. Не более 1+log2N с
Вставка в пирамиде Вставка. Добавить узел в конец и поднимать его выше Стоимость. Не более 1+log2N сравнений
Pic.27
Спуск в пирамиде Если родительский узел меньше одного (или двух) дочерних Поменять местами родительс
Спуск в пирамиде Если родительский узел меньше одного (или двух) дочерних Поменять местами родительский и больший дочерний узел Повторять до тех пор пока не будет восстановлена пирамидальная …
Pic.28
Удалить максимальный узел в пирамиде Удаление максимального узла. Поменять корень с последним узлом
Удалить максимальный узел в пирамиде Удаление максимального узла. Поменять корень с последним узлом и спустить его ниже Стоимость. Не более 2log2N сравнений
Pic.29
Бинарная пирамида Вставка. Добавить узел в конец и поднимать его выше Удаление максимального узла. П
Бинарная пирамида Вставка. Добавить узел в конец и поднимать его выше Удаление максимального узла. Поменять корень с последним узлом и спустить его ниже Видео 1
Pic.30
Бинарная пирамида: реализация на Java
Бинарная пирамида: реализация на Java
Pic.31
Реализация очереди с приоритетом
Реализация очереди с приоритетом
Pic.32
Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд 32
Pic.33
Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд 33
Pic.34
Пирамидальная сортировка (Heapsort)
Пирамидальная сортировка (Heapsort)
Pic.35
Пирамидальная сортировка Создать пирамиду из всех N ключей Повторять удаление максимального ключа
Пирамидальная сортировка Создать пирамиду из всех N ключей Повторять удаление максимального ключа
Pic.36
Пирамидальная сортировка
Пирамидальная сортировка
Pic.37
Пирамидальная сортировка Конструктор пирамиды. Создать max пирамиду восходящим методом Видео 2 Видео
Пирамидальная сортировка Конструктор пирамиды. Создать max пирамиду восходящим методом Видео 2 Видео 3
Pic.38
Пирамидальная сортировка: конструктор Первый проход. Создать пирамиду используя восходящий метод
Пирамидальная сортировка: конструктор Первый проход. Создать пирамиду используя восходящий метод
Pic.39
Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд 39
Pic.40
Пирамидальная сортировка Второй проход Удалять максимум поочередно Восстановить порядок в пирамиде
Пирамидальная сортировка Второй проход Удалять максимум поочередно Восстановить порядок в пирамиде
Pic.41
Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд 41
Pic.42
Пирамидальная сортировка: реализация на Java
Пирамидальная сортировка: реализация на Java
Pic.43
Пирамидальная сортировка
Пирамидальная сортировка
Pic.44
Пирамидальная сортировка
Пирамидальная сортировка
Pic.45
Пирамидальная сортировка: математический анализ Первый проход <= 2N сравнений и перестановок Втор
Пирамидальная сортировка: математический анализ Первый проход <= 2N сравнений и перестановок Второй проход <= 2N log2N сравнений и перестановок Значение. Алгоритм, не требующий дополнительной …
Pic.46
Алгоритмы сортировки
Алгоритмы сортировки


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!