Binary Heap на примере PriorityQueue в JAVA

Двоичная куча (binary heap) — это структура данных, которая представляет собой бинарное дерево, удовлетворяющее определённым условиям:

• Должна быть полным двоичным деревом:

  1. у каждого узла должно быть не более 2 дочерних элементов

  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:

здесь логика добавления будет такой же, только корневой элемент будет иметь максимальное значение.