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

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

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

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

Макс-куча

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

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

Мин-куча

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

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

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

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

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

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

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

Index	0	1	2	3	4	5	6	7	8	...
elements	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