Algoritmos: Insertar y Heapify.

Insertar

En el caso de tener un arreglo (array) ordenado en el algoritmo no se debe especificar ninguna posición, los elementos ocupan las posiciones que se les son asignadas según su valorDentro de este tipo de algoritmo pueden presentarse dos situaciones: Los elementos no pueden encontrarse repetidos en la lista. Los elementos pueden repetirse.

• Los elementos no pueden encontrarse repetidos en la lista: Al darse este caso dentro de la lista, nos arroga un mensaje o un código de error indicándonos que el elemento no se puede insertar. Si esto no sucede, se tendrá que buscar la posición que le corresponde en el arreglo y haga la inserción en la línea que le corresponde, que es de forma similar a la que se utiliza en el caso de arreglo no ordenados.

• Los elementos pueden repetirse: En este caso nos da igual que el elemento este o no en el arreglo. Simplemente utilizamos el método binario para que determine la posición donde se encuentra alojado el elemento o donde este debería estar, y en esta posición se debe insertar el nuevo número.

Algoritmo Heap Sort 

Una de las aplicaciones de los Heaps o Montículos es el algoritmo HeapSort, el cual es uno de tantos que permite ordenar un conjunto "S" de datos en tiempo “linearítmico“ O(n logn). No es un algoritmo estable, es decir, no garantiza que los elementos tengan el mismo orden relativo después de la ordenación, pero a diferencia de otros algoritmos comoQuicksort siempre garantiza O(n logn) como mejor, promedio o peor caso.

Una vez que se entiende la estructura de datos Heap el algoritmo es bastante sencillo y se basa en los siguientes pasos:

1.   Construir un MaxHeap o MinHeap a partir de un arreglo.

2.   Inicializar un ciclo desde I=heap.Length – 1 hasta I > 1 e Ir eliminando el tope (intercambiándolo con el último elemento I). Luego se verifica desde el primer nodo que se mantenga la propiedad del montículo (El mayor o menor elemento esté en el tope) esta operación generalmente se conoce como Heapify.

La explicación de eliminar del tope junto con Heapify puedes leerlas en mi post sobre Heaps o montículos, donde las explico con imágenes para que se entienda un poco mejor. Cabe destacar que para ordenar de manera creciente se utiliza un MaxHeap y para ordenar de manera decreciente un MinHeap. De igual manera, vale mencionar que la mayoría de las implementaciones de este algoritmo son en sitio, es decir, se modifica directamente el arreglo que se quiere ordenar.

Paso 1

Para construir el heap hay que recorrer el arreglo, recordemos que un montículo se basa un arreglo, desde (arreglo.Length / 2) hasta > 1. Se hace desde abajo hacia arriba porque a partir de (arreglo.Length) / 2 + 1 todos los nodos son hijos y en Heapify se deben verificar los nodos padres contra los hijos e ir intercambiando según sea el caso (con el mayor o el menor de los hijos) para mantener la propiedad del montículo. En Pseudocódigo sería algo como:

void BuildHeap(int[] array)

{

    for (int i = array.Length / 2; i <= 0; i--)

    {

        //Hacer cumplir la propiedad del heap dependiendo

        //si es un MaxHeap o un MinHeap

        Heapify(array, i, array.Length);

    }

}

Paso 2

Dentro de un ciclo vamos intercambiando el primer con el último elemento no ordenado y luego llamamos a Heapify para mantener la propiedad del Heap en la parte no ordenada del arreglo.