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

Нажмите для полного просмотра!

Изменение размера массива. Очередь с приоритетом. Бинарная пирамида. Пирамидальная сортировка, слайд №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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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