Algoritmo Heapsort

Definición de Montículo (Heap)

Un montículo es un árbol binario que cumple las siguientes condiciones:

• Es un árbol binario completo.
• Cada nodo es menor que todos sus descendientes (esto define un Min-Heap).

Observaciones Clave

• El mínimo está siempre en la raíz.
• Si un montículo tiene altura , puede tener como mucho nodos, y como poco nodos.
• No necesitamos punteros para su implementación.

Representación en Vector

Si ordenamos los nodos en un vector (como en el dibujo, dejando vacía la posición 0), podemos localizar al hijo izquierdo del nodo en la posición buscando en la posición del vector, y el hijo derecho estará en la .

Operación de Inserción (Insertar)

Ponemos el nodo en la última posición posible, es decir, en el primer hueco disponible del último nivel. Si quisiéramos insertar en nuestro ejemplo, pondríamos el nodo a insertar como hijo izquierdo de 20.

Después, comprobaríamos si es el valor del nodo. Si lo es, los cambiamos y comparamos el nodo con su nuevo padre, y así sucesivamente (proceso de heapify up). Si no lo es, lo dejamos como está.

Ejercicio Práctico

Ejercicio: Señalar detalladamente la evolución de los siguientes árboles binarios construidos por el método de Heapsort durante la ordenación de la lista siguiente: . Construyamos el montículo.

Ya tenemos el montículo, pero aún no la ordenación.

Operación de Borrar Mínimo (Borrar Raíz)

Borrar el mínimo es equivalente a borrar la raíz, ya que esta contiene el valor mínimo.

El procedimiento es el siguiente: Se toma el nodo que está más a la derecha en el último nivel (el último elemento del vector) y se coloca temporalmente en la raíz. Por ejemplo, si tuviéramos que recolocar el 7 y queremos borrar el 1.

Muevo el hueco y, mientras no pueda poner el nodo que tengo que recolocar (el 7) en el hueco, lo intercambio con el menor de sus hijos (proceso de heapify down).

Como ya no puedo bajar más, he de poner el ahí. El resultado es:

Así:

Estructura del Algoritmo Heapsort

El algoritmo de Heapsort consta de dos pasos principales:

1. Construir el montículo (Build Heap).
2. Aplicar la operación de Borrar Mínimo repetidamente hasta vaciar el montículo. Los elementos que se van extrayendo están ordenados, por lo tanto, se van almacenando o imprimiendo en orden.

Métodos para Construir Montículos

Podemos realizar la operación de insertar veces seguidas, o podemos realizar la siguiente operación más eficiente:

1. Construir un árbol binario completo con los datos.
2. Iterar desde el último nodo no hoja (generalmente N/2) hasta la raíz:

   For (i = N/2; i > 0; i--)
       Recolocar nodo i intercambiándolo con el menor de sus hijos (heapify down).

Ejercicios sobre Construcción

Ejercicio: Dado un árbol binario completo con nodos, ¿cuántos nodos habrá que recolocar como máximo para convertirlo en un montículo? Respuesta: 7.

Ejercicio: Obtener el orden de la lista por el método Heapsort.

Hay que recolocar los primeros: el , el , el y el .

Algoritmo Mergesort (Ordenación por Mezcla)

Mergesort es un algoritmo de ordenación basado en el paradigma Divide y Vencerás.

1. Dividir: Divide la lista en dos mitades recursivamente hasta llegar a listas de tamaño 1 (las cuales se consideran ordenadas).
2. Combinar (Mezclar): Para combinar las sublistas ordenadas, se sigue el siguiente procedimiento:

Proceso de Combinación

Llamamos lista I a una de ellas y lista D a la otra. Un índice i recorrerá la lista I y un índice j recorrerá la lista D. Se comparan I[i] con D[j]:

• Si I[i] es menor, se añade a una nueva lista R (resultado) y se incrementa i.
• Si D[j] es menor, se añade a R y se incrementa j.

Cuando se termina de recorrer una lista, se añade lo que queda de la otra lista a R, ya que esos elementos restantes ya están ordenados. Se sigue este proceso recursivamente hasta obtener la lista R de la longitud inicial, completamente ordenada.

Algoritmo Quicksort (Ordenación Rápida)

Quicksort es otro algoritmo de ordenación basado en Divide y Vencerás. Su funcionamiento se basa en la partición:

Elegimos un pivote y reordenamos la lista de tal manera que todos los elementos menores que el pivote queden a su izquierda y todos los mayores queden a su derecha. Este proceso se repite de manera recursiva en las sublistas resultantes.

Elección del Pivote

¿Cómo elegimos el pivote? Podríamos coger el elemento central, el primero o un número al azar, pero estas no siempre son las mejores elecciones para garantizar la eficiencia en el peor caso.

Sea V el vector que queremos ordenar, y sean p y r las posiciones que definen el subvector a ordenar. Por ejemplo, para la lista , deberíamos hacer Quicksort( ).

Quicksort(V, p, r)
Si (p < r) {
    q = Particionar(V, p, r);
    Quicksort(V, p, q - 1);
    Quicksort(V, q + 1, r);
}

Ejemplo de Partición

Ejemplo: Sea la lista .

Supongamos que elegimos el punto medio. El pivote será . (Podríamos utilizar otro método para calcularlo).

En nuestro ejemplo, el pivote es .

1. Vamos a incrementar el índice hasta encontrar un elemento mayor o igual que el pivote. Nos pararíamos en el , es decir, para .
2. Vamos a descender el índice desde el final hasta encontrar un elemento menor o igual que el pivote. Nos pararíamos en el , es decir, .
3. Intercambiamos por . Obtenemos .
4. Los índices y siguen en la misma posición y continúan avanzando hasta encontrar dos nuevos elementos (uno menor que el pivote y uno mayor que el pivote).

En nuestro ejemplo, el índice empezaría desde el (porque es donde estaba) y se para en porque encuentra el . El índice estaba en y baja hasta porque encuentra el . Los intercambiamos: .

Seguimos haciéndolo hasta que (puede que los índices se crucen).

Llegamos finalmente a .

Algoritmos de Búsqueda

Los algoritmos de búsqueda buscan un elemento (que llamaremos clave) en una lista de elementos.

Búsqueda Lineal (Secuencial)

Es el algoritmo más básico. Compara cada elemento de la lista con la clave hasta que la encuentra. Después, devuelve su posición.

Implementación (Pseudocódigo)

int buscar(int x, int A[]) {
    for (i = 0; i < N; i++) {
        if (A[i] == x) {
            return i; // Elemento encontrado
        }
    }
    return -1; // Elemento no encontrado
}

Para elementos de una lista, hemos de hacer como máximo comparaciones (en el peor caso).

Veamos otros algoritmos más eficientes.

Búsqueda Binaria

La condición indispensable para aplicar la búsqueda binaria es que la lista esté ordenada.

Es un algoritmo de Divide y Vencerás:

1. Elegimos el punto medio de la lista.
2. Si el elemento a buscar es el punto medio, devolvemos su posición.
3. Si la clave es menor que el punto medio, elegimos la sublista de la izquierda y repetimos el proceso.
4. Si la clave es mayor que el punto medio, elegimos la sublista de la derecha y repetimos.