Удалите самый большой/самый маленький элемент.
API, которые мы ищем:
* Вставлять
* Удалить
* Найти следующий максимум
Реализации, которые мы можем придумать:
* Неупорядоченный массив: O(1) для вставки, O(N) для удаления, O(N) для поиска следующего максимума
* Упорядоченный массив: O(N) для вставки, O(1) для удаления, O(1) для поиска следующего максимума
* Двоичная куча/полные двоичные деревья: O(logN) для вставки, O(logN) для удаления, O(logN) для поиска следующего максимума
Двоичные кучи:
Двоичные кучи используются в приоритетных очередях. Это в основном потому, что они занимают гораздо меньше места. Хранение и сортировка всех данных для нахождения наибольшего потребует NlogN времени и N пространства.
Порядок в куче: Родительский ключ не меньше, чем дочерние ключи.
Самый большой ключ находится в первом индексе массива.
Родительский узел k находится на k/2
Дочерними элементами узла k являются 2k и 2k+1.
Сценарий 1: Дочерний ключ становится больше, чем ключ его родителя.
Для устранения нарушения:
- Обмен ключа в дочернем с ключом в родительском.
- Повторяйте, пока порядок кучи не восстановится.
Сценарий 2. Родительский ключ становится меньше одного (или обоих) дочернего ключа.
Для устранения нарушения:
- Обмен ключа в родительском с ключом в более крупном дочернем элементе.
- Повторяйте, пока порядок кучи не восстановится.
Как внедрить API Priority Queue?
- Вставка: добавьте узел в конце, а затем поднимите его вверх.
Не более 1 + lg N сравнивает. - Удалить: поменять местами корень с узлом в конце, а затем понизить его.
Не более 2 lg N сравнивается.
