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

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

Поскольку элементы кучи хранятся в массиве, учитывая начальный индекс как 1, положение родительского узла ith элемент можно найти на ⌊ i/2 ⌋. Левый и правый дочерние элементыith узел находится в позиции 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