DAA: montón binario

Hay varios tipos de montones, sin embargo, en este capítulo, vamos a discutir el montón binario. UNAbinary heapes una estructura de datos, que se parece a un árbol binario completo. La estructura de datos del montón obedece a las propiedades de ordenación que se describen a continuación. Generalmente, un montón se representa mediante una matriz. En este capítulo, estamos representando un montón porH.

Como los elementos de un montón se almacenan en una matriz, considerando el índice inicial como 1, la posición del nodo padre de i^th El elemento se puede encontrar en ⌊ i/2 ⌋. Hijo izquierdo y hijo derecho dei^th el nodo está en la posición 2i y 2i + 1.

Un montón binario se puede clasificar además como un max-heap o un min-heap basado en la propiedad de pedido.

Max-Heap

En este montón, el valor de clave de un nodo es mayor o igual que el valor de clave del hijo más alto.

Por lo tanto, H[Parent(i)] ≥ H[i]

Min-Heap

En mean-heap, el valor de clave de un nodo es menor o igual que el valor de clave del hijo más bajo.

Por lo tanto, H[Parent(i)] ≤ H[i]

En este contexto, las operaciones básicas se muestran a continuación con respecto a Max-Heap. La inserción y eliminación de elementos en y desde montones necesita una reorganización de elementos. Por lo tanto,Heapify la función necesita ser llamada.

Representación de matriz

Un árbol binario completo se puede representar mediante una matriz, almacenando sus elementos utilizando el orden de nivel transversal.

Consideremos un montón (como se muestra a continuación) que estará representado por una matriz H.

Considerando el índice inicial como 0, utilizando el orden de nivel transversal, los elementos se mantienen en una matriz de la siguiente manera.

En este contexto, las operaciones en el montón se representan con respecto a Max-Heap.

Para encontrar el índice del padre de un elemento en el índice i, el siguiente algoritmo Parent (numbers[], i) se utiliza.

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

El índice del hijo izquierdo de un elemento en el índice i se puede encontrar usando el siguiente algoritmo, Left-Child (numbers[], i).

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

El índice del hijo derecho de un elemento en el índice i se puede encontrar usando el siguiente algoritmo, Right-Child(numbers[], i).

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