DAA - двоичная куча

Существует несколько типов куч, однако в этой главе мы собираемся обсудить двоичную кучу. Бинарная куча - это структура данных, которая выглядит как полное двоичное дерево. Структура данных кучи подчиняется свойствам упорядочения, описанным ниже. Как правило, куча представлена массивом. В этой главе мы представляем кучу H.

Поскольку элементы кучи хранятся в массиве, учитывая начальный индекс как 1 , положение родительского узла i- го элемента можно найти в ⌊ i / 2 ⌋ . Левый и правый дочерние элементы i- го узла находятся в положениях 2i и 2i + 1 .

Двоичная куча может быть классифицирована далее как максимальная куча или минимальная куча на основе свойства упорядочения.

Max-Heap

В этой куче значение ключа узла больше или равно значению ключа самого высокого дочернего элемента.

Следовательно, H [Parent (i)] ≥ H [i]

Max-Heap

Min-Heap

В средней куче значение ключа узла меньше или равно значению ключа самого нижнего потомка.

Следовательно, H [Parent (i)] ≤ H [i]

В этом контексте основные операции показаны ниже относительно Max-Heap. Для вставки и удаления элементов в кучах и из них требуется перестановка элементов. Следовательно, функция Heapify должна быть вызвана.

Min-Heap

Представление массива

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

Давайте рассмотрим кучу (как показано ниже), которая будет представлена массивом H.

Представление массива

Рассматривая начальный индекс как 0 , используя обход уровня, элементы сохраняются в массиве следующим образом.

Показатель 0 1 2 3 4 5 6 7 8 ...
элементы 70 30 50 12 20 35 25 4 8 ...

В этом контексте операции с кучей представляются в отношении Max-Heap.

Чтобы найти индекс родителя элемента по индексу i , используется следующий алгоритм Parent (numbers [], i) .

 Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

Индекс левого потомка элемента с индексом i можно найти с помощью следующего алгоритма Left-Child (numbers [], i) .

 Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL 

Индекс правого потомка элемента с индексом i можно найти с помощью следующего алгоритма Right-Child (numbers [], i) .

 Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL