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

Июль 27, 2022

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

Содержание

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

Слайд 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
Рандомизированная очередь. Удаляется случайный элемент
Очередь с приоритетом. Удаляется самый большой (или маленький) элемент

Слайд 12

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

Слайд 13

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

Слайд 14

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

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

Слайд 15

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

Слайд 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

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

Слайд 32

Слайд 33

Слайд 34

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

Слайд 35

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

Слайд 36

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

Слайд 37

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

Слайд 38

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

Слайд 39

Слайд 40

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

Слайд 41

Слайд 42

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

Слайд 43

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

Слайд 44

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

Слайд 45

Пирамидальная сортировка: математический анализ
Первый проход <= 2N сравнений и перестановок
Второй проход

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

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

Содержание

Стек: изменение размера массиваПроблема. От клиента требуется указывать размер стекаКак увеличивать

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

Стек: амортизированная стоимость добавления в стекСтоимость добавления первых N элементов: N

Стек: изменение размера массиваКак изменять размер массива?Первый подходpush(): увеличивать размер массива

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Полное бинарное деревоБинарное дерево. Пустота или узел с левым и правым

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пирамидальная сортировка: математический анализПервый проход <= 2N сравнений и перестановокВторой проход

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

Стек: изменение размера массива
Проблема. От клиента требуется указывать размер стека
Как увеличивать

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

Стек: амортизированная стоимость добавления в стек
Стоимость добавления первых N элементов: N

Стек: изменение размера массива
Как изменять размер массива?
Первый подход
push(): увеличивать размер массива

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

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

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

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

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

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

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

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

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

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

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

Полное бинарное дерево
Бинарное дерево. Пустота или узел с левым и правым

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

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

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

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

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

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

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

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

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

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

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

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

Пирамидальная сортировка: математический анализ
Первый проход <= 2N сравнений и перестановок
Второй проход