Краткое объяснение!
Максимальная двоичная куча:
- Полное двоичное дерево, в котором родительские узлы всегда больше, чем дочерние узлы.
- Каждый родитель имеет не более двух дочерних узлов.
- Родитель всегда больше, чем его дети, но нет никаких гарантий между родственными узлами.
- Поскольку это полное бинарное дерево, оно максимально компактно. Все дочерние элементы каждого узла заполнены настолько, насколько это возможно, а левые дочерние элементы заполняются первыми.
Отношения между родительскими и дочерними узлами:
- Если узел находится в индексе - i
- Левый дочерний элемент находится в - 2*i + 1
- Правильный дочерний элемент - 2*i + 2
- Для любого дочернего элемента с индексом 'i'родитель находится на уровне - floor((i-1) / 2)
Примечание.в данном случае мы предполагаем, что начальный индекс равен 0
Максимальный класс двоичной кучи:
- Мы определяем наш класс MaxBinaryHeap
- Единственное свойство, которое требуется в конструкторе, — это свойство значений, которое может быть пустым списком/массивом.
class Name:
MaxBinaryHeap
properties:
values = []
Вставить в максимальную двоичную кучу
TL;DR — Добавить в конец и поднять вверх.
Псевдокод:
- Поместите значение свойства values в кучу.
- Поднимите значение до нужного места.
- Всплывающие вверх:
- Создайте новую переменную с именем index, в которой будет храниться индекс последнего элемента массива значений. (values.length-1).
- Создайте переменную parentIndex для хранения индекса родителя текущей переменной.
- Продолжайте цикл до тех пор, пока значение элемента в parentIndex меньше значения элемента в дочернем индексе.
- Поменяйте местами значения элементов в parentIndex и дочернем индексе.
- Установите индекс как parentIndex и начните сначала.
Извлечение из кучи (extract max)
TL;DR:
- Удалить корень.
- Замените последним добавленным узлом.
- Настройте корень. (утонуть)
Псевдокод:
- Замените первое значение свойства values на последнее.
- Выталкивайте из свойства values, чтобы вы могли вернуть значение в конце.
- Пусть новый корень опустится в нужное место:
- Родительский индекс начинается с 0 (корень)
- Найдите индекс левого дочернего элемента:2*index + 1.
- Найдите индекс правого дочернего элемента:2*index + 2
- Если левый или правый дочерний элемент больше, чем элемент, то заменяется местами. Если оба дочерних элемента left и right больше, поменяйте местами с >самый крупный ребенок.
- Дочерний индекс, на который вы переключились, теперь становится новым родительским индексом.
- Продолжайте зацикливаться и менять местами, пока ни один из дочерних элементов не станет больше, чем элемент.
- Верните старый корень.
Временная сложность:
- Вставка:O(log(n))
- Удаление:O(log(n))
- Построение кучи:O(n)
Полный код
Также читайте
