Estructuras de datos de montón
Heap es un caso especial de estructura de datos de árbol binario balanceada donde la clave del nodo raíz se compara con sus hijos y se organiza en consecuencia. Siα tiene nodo hijo β entonces -
tecla (α) ≥ tecla (β)
Como el valor de parent es mayor que el de child, esta propiedad genera Max Heap. Según este criterio, un montón puede ser de dos tipos:
For Input → 35 33 42 10 14 19 27 44 26 31
Min-Heap - Donde el valor del nodo raíz es menor o igual que cualquiera de sus hijos.
Max-Heap - Donde el valor del nodo raíz es mayor o igual que cualquiera de sus hijos.
Ambos árboles se construyen utilizando la misma entrada y el mismo orden de llegada.
Algoritmo de construcción de montón máximo
Usaremos el mismo ejemplo para demostrar cómo se crea un Max Heap. El procedimiento para crear Min Heap es similar, pero optamos por valores mínimos en lugar de valores máximos.
Vamos a derivar un algoritmo para el montón máximo insertando un elemento a la vez. En cualquier momento, el montón debe mantener su propiedad. Durante la inserción, también asumimos que estamos insertando un nodo en un árbol ya acumulado.
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Note - En el algoritmo de construcción Min Heap, esperamos que el valor del nodo principal sea menor que el del nodo secundario.
Entendamos la construcción de Max Heap mediante una ilustración animada. Consideramos la misma muestra de entrada que usamos anteriormente.
Algoritmo de eliminación de montón máximo
Derivemos un algoritmo para eliminar del montón máximo. La eliminación en el montón máximo (o mínimo) siempre ocurre en la raíz para eliminar el valor máximo (o mínimo).
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.