Двоичная куча (binary heap) — это структура данных, которая представляет собой бинарное дерево, удовлетворяющее определённым условиям:
-
Должна быть полным двоичным деревом:
-
у каждого узла должно быть не более 2 дочерних элементов
-
уровни заполняются слева направо
-
-
Значение каждого родителя ≤ значений его детей (≥ для max-heap)
Возможны 2 реализации:
min-heap - корень имеет минимальное значение (приоритет минимального значения)
max-heap - корень имеет максимальное значение (приоритет максимального значения)
В PriorityQueue данные хранятся в виде массива.
В конструкторе по умолчанию initialCapacity = 11.
Индекс позиций элементов определяется по следующим формулам:
-
Для родителя:
(i-1)/2(где i - индекс дочернего элемента, а остаток от деления отбрасывается) -
Для левого потомка:
2*i+1(где i - индекс родительского элемента) -
Для правого потомка:
2*i+2(где i - индекс родительского элемента)
Пример внесения данных в такую структуру на примере min-heap:
В конструкторе по умолчанию создается массив с длиной 11:
Добавляется элемент 6 и занимает место корневого:
Добавляется элемент 1. Вычисляется позиция для левого потомка элемента под индексом 0: 2*0+1=1
Т.к. 1 < 6, а родительский узел всегда должен быть минимальным значением, элементы меняются местами.
Добавляется элемент 2. Вычисляется позиция для правого потомка элемента под индексом 0: 2*0+2=2
Добавляется элемент 4. Вычисляется позиция для левого потомка элемента под индексом 1: 2*1+1=3
Т.к. узел должен начинаться с самого левого края и родительский узел всегда должен быть минимальным значением, элементы меняются местами.
Добавляется элемент 0. Вычисляется позиция для левого потомка элемента под индексом 2: 2*2+1=5
Т.к. родительский узел всегда должен быть минимальным значением, элементы 0 и 2, а затем 0 и 1 меняются местами.
Пример внесения данных в такую структуру на примере max-heap:
здесь логика добавления будет такой же, только корневой элемент будет иметь максимальное значение.
Автор: nadillustrator
