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

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

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

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

Pic.1

Изменение размера массива

Pic.2

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

Pic.3

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

Pic.4

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

Pic.5

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

Pic.6

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

Pic.7

Стек: изменение размера массива

Pic.8

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

Pic.9

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

Pic.10

Очередь с приоритетом (Priority Queue)

Pic.11

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

Pic.12

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

Pic.13

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

Pic.14

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

Pic.15

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

Pic.16

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

Pic.17

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

Pic.18

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

Pic.19

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

Pic.20

Бинарная пирамида (Binary Heaps)

Pic.21

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

Pic.22

Полное бинарное дерево

Pic.23

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

Pic.24

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

Pic.25

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

Pic.26

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

Pic.27

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

Pic.28

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

Pic.29

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

Pic.30

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

Pic.31

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

Pic.32

Pic.33

Pic.34

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

Pic.35

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

Pic.36

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

Pic.37

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

Pic.38

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

Pic.39

Pic.40

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

Pic.41

Pic.42

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

Pic.43

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

Pic.44

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

Pic.45

Пирамидальная сортировка: математический анализ Первый проход <= 2N сравнений и перестановок Второй проход <= 2N log2N сравнений и перестановок Значение. Алгоритм, не требующий дополнительной …

Pic.46

Алгоритмы сортировки

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

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