![Куча на массиве
полное двоичное дерево: уровни заполняются слева
направо; все уровни заполнены полностью, кроме,
возможно, последнего
естественная нумерация вершин: сверху вниз, слева
направо
при добавлении элемента подвешиваем лист на
последний уровень; при удалении отрезаем самый
последний лист
вершина i имеет родителя ⌊i/2⌋ и детей 2i и 2i + 1
(при вычислении данных индексов нужно проверять,
что они попадают в отрезок [1, n])
11 / 11](https://image.slidesharecdn.com/2-greedy-3-heaps-151122095125-lva1-app6892/85/-32-320.jpg)
![Куча на массиве
полное двоичное дерево: уровни заполняются слева
направо; все уровни заполнены полностью, кроме,
возможно, последнего
естественная нумерация вершин: сверху вниз, слева
направо
при добавлении элемента подвешиваем лист на
последний уровень; при удалении отрезаем самый
последний лист
вершина i имеет родителя ⌊i/2⌋ и детей 2i и 2i + 1
(при вычислении данных индексов нужно проверять,
что они попадают в отрезок [1, n])
не нужно хранить указатели на родителя и детей
11 / 11](https://image.slidesharecdn.com/2-greedy-3-heaps-151122095125-lva1-app6892/85/-33-320.jpg)
![Куча на массиве
полное двоичное дерево: уровни заполняются слева
направо; все уровни заполнены полностью, кроме,
возможно, последнего
естественная нумерация вершин: сверху вниз, слева
направо
при добавлении элемента подвешиваем лист на
последний уровень; при удалении отрезаем самый
последний лист
вершина i имеет родителя ⌊i/2⌋ и детей 2i и 2i + 1
(при вычислении данных индексов нужно проверять,
что они попадают в отрезок [1, n])
не нужно хранить указатели на родителя и детей
глубина кучи есть O(log n), поэтому все операции
работают за время O(log n)
11 / 11](https://image.slidesharecdn.com/2-greedy-3-heaps-151122095125-lva1-app6892/85/-34-320.jpg)
More Related Content
More from DEVTYPE (20)
Кучи
- 1. Жадные алгоритмы: кучи Александр Куликов Онлайн-курс «Алгоритмы: теория и практика. Методы» http://stepic.org/217
- 2. Очередь с приоритетами Insert(p) добавляет новый элемент с приоритетом p Remove(it) удаляет элемент, на который указывает итератор it GetMin() возвращает элемент с минимальным приоритетом ExtractMin() извлекает из очереди элемент с минимальным приоритетом ChangePriority(it, p) изменяет приоритет элемента, на который указывает итератор it, на p 2 / 11
- 3. Простейшие реализации массив: GetMin имеет время работы O(n) 3 1 5 4 2 3 / 11
- 4. Простейшие реализации массив: GetMin имеет время работы O(n) 3 1 5 4 2 упорядоченный массив: GetMin — O(1), Remove — O(n) 1 2 3 4 5 3 / 11
- 5. Простейшие реализации массив: GetMin имеет время работы O(n) 3 1 5 4 2 упорядоченный массив: GetMin — O(1), Remove — O(n) 1 2 3 4 5 упорядоченный список: GetMin and Remove — O(1), Insert — O(n) 1 2 3 4 5 3 / 11
- 6. Двоичная (мин-)куча 4 20 22 21 53 7 18 18 42 основное свойство (мин-)кучи: значение вершины ≤ значений её детей минимальное значение хранится в корне, поэтому GetMin работает за время O(1) 4 / 11
- 7. Вставка и просеивание вверх 4 20 22 21 53 7 18 18 42 5 подвесим новый элемент листом в произвольное место 5 / 11
- 8. Вставка и просеивание вверх 4 20 22 21 53 7 18 18 42 5 подвесим новый элемент листом в произвольное место начнём чинить свойство кучи, просеивая проблемную вершину вверх 5 / 11
- 9. Вставка и просеивание вверх 4 20 22 21 53 7 18 18 5 42 подвесим новый элемент листом в произвольное место начнём чинить свойство кучи, просеивая проблемную вершину вверх 5 / 11
- 10. Вставка и просеивание вверх 4 20 22 21 53 7 18 18 5 42 подвесим новый элемент листом в произвольное место начнём чинить свойство кучи, просеивая проблемную вершину вверх 5 / 11
- 11. Вставка и просеивание вверх 4 20 22 21 53 7 5 18 18 42 подвесим новый элемент листом в произвольное место начнём чинить свойство кучи, просеивая проблемную вершину вверх 5 / 11
- 12. Вставка и просеивание вверх 4 20 22 21 53 5 7 18 18 42 подвесим новый элемент листом в произвольное место начнём чинить свойство кучи, просеивая проблемную вершину вверх 5 / 11
- 13. Время работы операции вставки важный инвариант: в каждый момент времени свойство кучи нарушено не более чем в одной вершине 6 / 11
- 14. Время работы операции вставки важный инвариант: в каждый момент времени свойство кучи нарушено не более чем в одной вершине при просеивании вверх эта вершина становится ближе к корню 6 / 11
- 15. Время работы операции вставки важный инвариант: в каждый момент времени свойство кучи нарушено не более чем в одной вершине при просеивании вверх эта вершина становится ближе к корню время работы есть O(h), где h — высота кучи 6 / 11
- 16. Извлечение минимума и просеивание вниз 4 20 22 21 53 7 18 18 42 заменим корень на любой лист 7 / 11
- 17. Извлечение минимума и просеивание вниз 53 20 22 21 7 18 18 42 заменим корень на любой лист 7 / 11
- 18. Извлечение минимума и просеивание вниз 53 20 22 21 7 18 18 42 заменим корень на любой лист 7 / 11
- 19. Извлечение минимума и просеивание вниз 7 20 22 21 53 18 18 42 заменим корень на любой лист обменяем проблемную вершину с меньшим из её детей, чтобы быть уверенными, что продолжать чинить кучу нужно только в одном из поддеревьев 7 / 11
- 20. Извлечение минимума и просеивание вниз 7 20 22 21 53 18 18 42 заменим корень на любой лист обменяем проблемную вершину с меньшим из её детей, чтобы быть уверенными, что продолжать чинить кучу нужно только в одном из поддеревьев 7 / 11
- 21. Извлечение минимума и просеивание вниз 7 20 22 21 18 53 18 42 заменим корень на любой лист обменяем проблемную вершину с меньшим из её детей, чтобы быть уверенными, что продолжать чинить кучу нужно только в одном из поддеревьев 7 / 11
- 22. Извлечение минимума и просеивание вниз 7 20 22 21 18 53 18 42 заменим корень на любой лист обменяем проблемную вершину с меньшим из её детей, чтобы быть уверенными, что продолжать чинить кучу нужно только в одном из поддеревьев 7 / 11
- 23. Извлечение минимума и просеивание вниз 7 20 22 21 18 18 53 42 заменим корень на любой лист обменяем проблемную вершину с меньшим из её детей, чтобы быть уверенными, что продолжать чинить кучу нужно только в одном из поддеревьев время работы: O(h) 7 / 11
- 24. Изменение приоритета 4 20 22 21 53 7 18 18 42 8 / 11
- 25. Изменение приоритета 4 20 22 21 53 7 18 18 42 изменим приоритет и дадим элементу просеиться вниз или вверх 8 / 11
- 26. Удаление 4 20 22 21 53 7 18 18 42 9 / 11
- 27. Удаление 4 20 22 21 53 7 18 18 42 изменим приоритет элемента на −∞, просеим его вверх и извлечём минимум 9 / 11
- 28. Полное двоичное дерево и массив 4 1 18 2 20 4 53 8 22 9 21 5 7 3 18 6 42 7 4 1 18 2 7 3 20 4 21 5 18 6 42 7 53 8 22 9 10 / 11
- 29. Куча на массиве полное двоичное дерево: уровни заполняются слева направо; все уровни заполнены полностью, кроме, возможно, последнего 11 / 11
- 30. Куча на массиве полное двоичное дерево: уровни заполняются слева направо; все уровни заполнены полностью, кроме, возможно, последнего естественная нумерация вершин: сверху вниз, слева направо 11 / 11
- 31. Куча на массиве полное двоичное дерево: уровни заполняются слева направо; все уровни заполнены полностью, кроме, возможно, последнего естественная нумерация вершин: сверху вниз, слева направо при добавлении элемента подвешиваем лист на последний уровень; при удалении отрезаем самый последний лист 11 / 11
- 32. Куча на массиве полное двоичное дерево: уровни заполняются слева направо; все уровни заполнены полностью, кроме, возможно, последнего естественная нумерация вершин: сверху вниз, слева направо при добавлении элемента подвешиваем лист на последний уровень; при удалении отрезаем самый последний лист вершина i имеет родителя ⌊i/2⌋ и детей 2i и 2i + 1 (при вычислении данных индексов нужно проверять, что они попадают в отрезок [1, n]) 11 / 11
- 33. Куча на массиве полное двоичное дерево: уровни заполняются слева направо; все уровни заполнены полностью, кроме, возможно, последнего естественная нумерация вершин: сверху вниз, слева направо при добавлении элемента подвешиваем лист на последний уровень; при удалении отрезаем самый последний лист вершина i имеет родителя ⌊i/2⌋ и детей 2i и 2i + 1 (при вычислении данных индексов нужно проверять, что они попадают в отрезок [1, n]) не нужно хранить указатели на родителя и детей 11 / 11
- 34. Куча на массиве полное двоичное дерево: уровни заполняются слева направо; все уровни заполнены полностью, кроме, возможно, последнего естественная нумерация вершин: сверху вниз, слева направо при добавлении элемента подвешиваем лист на последний уровень; при удалении отрезаем самый последний лист вершина i имеет родителя ⌊i/2⌋ и детей 2i и 2i + 1 (при вычислении данных индексов нужно проверять, что они попадают в отрезок [1, n]) не нужно хранить указатели на родителя и детей глубина кучи есть O(log n), поэтому все операции работают за время O(log n) 11 / 11