09 Піраміди
•
0 likes•12,597 views
Слайди лекції з курсу "Розробка та аналіз алгоритмів. Частина 1". Тема лекції: "Піраміди". http://edx.prometheus.org.ua/courses/KPI/Algorithms101/2015_Spring/about
09 Піраміди
- 1. Розробка та аналіз алгоритмів 9. Піраміди • Функціонування пірамід • Пірамідальне сортування • Черги з пріоритетами (с) Олексій Молчановський, Prometheus.org.ua 1
- 2. Означення піраміди (с) Олексій Молчановський, Prometheus.org.ua 2
- 3. Типи пірамід (с) Олексій Молчановський, Prometheus.org.ua 3
- 4. Основні операції • Підтримка властивості піраміди – O(lgn) • Створення піраміди – O(n) • Пірамідальне сортування – O(n lgn) • Використання піраміди в якості черги з пріоритетами – O(lgn) (с) Олексій Молчановський, Prometheus.org.ua 4
- 5. Підтримка властивості піраміди (с) Олексій Молчановський, Prometheus.org.ua 5
- 6. Підтримка властивості піраміди (с) Олексій Молчановський, Prometheus.org.ua 6
- 7. Створення піраміди (с) Олексій Молчановський, Prometheus.org.ua 7
- 8. Створення піраміди (с) Олексій Молчановський, Prometheus.org.ua 8
- 9. Створення піраміди (с) Олексій Молчановський, Prometheus.org.ua 9
- 10. Створення піраміди. Аналіз алгоритму (с) Олексій Молчановський, Prometheus.org.ua 10
- 11. Пірамідальне сортування (с) Олексій Молчановський, Prometheus.org.ua 11
- 12. Пірамідальне сортування (с) Олексій Молчановський, Prometheus.org.ua 12
- 13. Черги з пріоритетами • Черга з пріоритетом – це множина S, в якій кожний елемент має ключ у вигляді числа • Незростаюча черга • Приклад. Задачі (процеси) для виконання ОС. Задачі впорядковані за спаданням пріоритетів • Неспадна черга • Приклад. Події, які моделюються. Всі події впорядковані за зростанням горизонту (часу) виконання (с) Олексій Молчановський, Prometheus.org.ua 13
- 14. Черги з пріоритетами. Базові операції • Вставка елементу (Insert) – додає елемент до черги • Визначення максимального елементу (Maximum) – повертає значення найбільшого елементу черги • Видалення максимального елементу (ExtractMax) – видаляє та повертає найбільший елемент з черги • Збільшення ключа для елементу (IncreaseKey) – збільшує значення ключа для заданого елементу черги (с) Олексій Молчановський, Prometheus.org.ua 14
- 15. Черги з пріоритетами. Базові операції (с) Олексій Молчановський, Prometheus.org.ua 15
- 16. Черги з пріоритетами. Базові операції (с) Олексій Молчановський, Prometheus.org.ua 16