Complejidad de tiempo Heapsort

Un montón se denomina 'parcialmente ordenado' y no 'parcialmente ordenado'. La palabra “ordenar” significa ordenamiento completo (complete sorting). Un montón no se ordena parcialmente de forma arbitraria. Un montón se ordena parcialmente siguiendo un criterio (patrón), como se muestra a continuación.

Entonces, heapsort consta de dos etapas: construir el montón y extraer el elemento ordenado de la parte superior del montón. En la segunda etapa, después de cada extracción, se reconstruye el montón. Cada reconstrucción es más rápida que el proceso de construcción original, ya que la reconstrucción se realiza a partir de una construcción anterior, en la que se ha eliminado un elemento. Y con eso, heapsort ordena una lista completamente desordenada.

El objetivo de este artículo es explicar brevemente heapsort y luego producir su complejidad de tiempo (vea el significado de complejidad de tiempo a continuación). Hacia el final, la codificación se realiza en C++.

Montón mínimo

Un montón puede ser un montón mínimo o un montón máximo. Un montón máximo es aquel en el que el primer elemento es el elemento más alto y todo el árbol o la lista correspondiente se ordena parcialmente en orden descendente. Un montón mínimo es aquel en el que el primer elemento es el elemento mínimo y la lista completa está parcialmente ordenada en orden ascendente. En este artículo, solo se considera el montón mínimo. Nota: en el tema del montón, un elemento también se denomina nodo.

Un montón es un árbol binario completo. El árbol binario se puede expresar como una matriz (lista); leer de arriba a abajo y de izquierda a derecha. La propiedad del montón para un montón mínimo es que un nodo padre es menor o igual que cada uno de sus dos hijos. Un ejemplo de una lista desordenada es:

La primera fila de esta tabla son los elementos de la matriz. En la segunda fila están los índices de base cero. Esta lista de elementos se puede expresar como un árbol. Los elementos nulos se han agregado para hacer un árbol binario completo. En sentido estricto, los elementos nulos no forman parte de la lista (árbol). Esta lista no tiene orden, por lo que aún no es un montón. Se convertirá en un montón cuando haya tenido un ordenamiento parcial, según la propiedad del montón.

Relación entre nodos e índices

Recuerde, un montón es un árbol binario completo antes de tener la configuración del montón (propiedad del montón). La lista anterior aún no es un montón, porque los elementos no obedecen la propiedad del montón. Se convierte en un montón después de reorganizar los elementos en un orden parcial de acuerdo con la propiedad min-heap. El orden parcial puede verse como una ordenación parcial (aunque la palabra 'ordenar' significa una ordenación completa).

Ya sea que un árbol binario sea un montón o no, cada padre tiene dos hijos, excepto los nodos hoja (últimos). Existe una relación matemática entre los índices entre cada padre y sus hijos. Es como sigue: si el padre está en el índice i, entonces el hijo izquierdo está en el índice:

y el niño correcto está en el índice:

Esto es para la indexación basada en cero. Y así, un padre en el índice 0 tiene su hijo izquierdo en el índice 2×0+1=1 y su hijo derecho en 2×0+2=2. Un padre en el índice 1 tiene su hijo izquierdo en el índice 2×1+1=3 y su hijo derecho en el índice 2×1+2=4; y así.

Por la propiedad min-heap, un padre en i es menor o igual que el hijo izquierdo en 2i+1 y menor o igual que el hijo derecho en 2i+2.

Montón

Heapificar significa construir un montón. Significa reorganizar los elementos de una lista (o el árbol correspondiente) para que satisfagan la propiedad del montón. Al final del proceso de acumulación, la lista o árbol es un montón.

Si se acumula la lista desordenada anterior, se convertirá en:

Nota: hay 12 elementos y no 15 en la lista. En la segunda fila están los índices. En el proceso de construcción del montón, los elementos debían verificarse y algunos intercambiarse.

Fíjate que el primer y más pequeño elemento es el 3. El resto de los elementos le siguen de forma ascendente pero ondulante. Si los hijos izquierdo y derecho en las posiciones 2i+1 y 2i+2 son mayores o iguales que el padre en i, entonces se trata de un montón mínimo. Esto no es ordenar o clasificar por completo. Esta es una ordenación parcial, de acuerdo con la propiedad del montón. Es a partir de aquí que comienza la siguiente etapa para la ordenación del montón.

Complejidad del tiempo de Heapify

La complejidad del tiempo es el tiempo de ejecución relativo de algún código. Se puede ver como el número de operaciones principales para que se complete ese código. Hay diferentes algoritmos para la construcción de montones. Los más eficientes y rápidos dividen continuamente la lista por dos, verifican los elementos desde la parte inferior y luego intercambian algunos elementos. Sea N el número de elementos prácticos de la lista. Con este algoritmo, el número máximo de operaciones principales (intercambio) es N. La complejidad de tiempo para acumular se da anteriormente como:

Donde n es N y es el máximo número posible de operaciones principales. Esta notación se llama notación Big-O. Comienza con O en mayúscula, seguido de paréntesis. Dentro de los paréntesis está la expresión para el mayor número posible de operaciones.

Recuerda: la suma puede convertirse en multiplicación si se repite lo mismo que se suma.

Ilustración de heapsort

La lista desordenada anterior se usará para ilustrar la ordenación en montón. La lista dada es:

El montón mínimo producido a partir de la lista es:

La primera etapa en heapsort es producir el montón que se ha producido. Esta es una lista parcialmente ordenada. No es una lista ordenada (completamente ordenada).

La segunda etapa consiste en eliminar el elemento mínimo, que es el primer elemento, del montón, volver a acumular el montón restante y eliminar los elementos mínimos en los resultados. El elemento mínimo es siempre el primer elemento en el montón re-amontonado. Los elementos no se quitan ni se tiran. Se pueden enviar a una matriz diferente en el orden en que se eliminan.

Al final, la nueva matriz tendría todos los elementos ordenados (completamente), en orden ascendente; y ya no sólo parcialmente ordenada.

En la segunda etapa, lo primero que debe hacer es eliminar 3 y colocarlo en la nueva matriz. Los resultados son:

y

Los elementos restantes deben amontonarse antes de extraer el primer elemento. El montón de los elementos restantes puede convertirse en:

Extraer 5 y agregar a la nueva lista (matriz) da los resultados:

y

Amontonar el conjunto restante daría:

Extraer 6 y agregar a la nueva lista (matriz) da los resultados:

y

Amontonar el conjunto restante daría:

Extraer 7 y agregarlo a la nueva lista da los resultados:

y

Al amontonar el conjunto restante se obtiene:

Extrayendo 9 y agregando a la nueva lista, da los resultados:

y

Al amontonar el conjunto restante se obtiene:

Extraer 11 y agregarlo a la nueva lista da los resultados:

y

Amontonar el conjunto restante daría:

Extraer 14 y agregarlo a la nueva lista da los resultados:

y

Amontonar el conjunto restante daría:

Extraer 15 y agregarlo a la nueva lista da los resultados:

y

Amontonar el conjunto restante daría:

Extraer 17 y agregarlo a la nueva lista da los resultados:

y

Amontonar el conjunto restante daría:

Extraer 19 y agregarlo a la nueva lista da los resultados:

y

Al amontonar el conjunto restante se obtiene:

Extraer 22 y agregarlo a la nueva lista da los resultados:

y

Al acumular el conjunto restante se obtiene:

Extraer 24 y agregarlo a la nueva lista da los resultados:

y

La matriz de almacenamiento dinámico ahora está vacía. Todos los elementos que tenía al principio ahora están en la nueva matriz (lista) y ordenados.

Algoritmo Heapsort

Aunque el lector puede haber leído en los libros de texto que heapsort consta de dos etapas, todavía se puede considerar que consiste en una etapa, que reduce iterativamente la matriz dada. Con eso, el algoritmo para ordenar con heapsort es el siguiente:

• Apile la lista desordenada.
• Extraiga el primer elemento del montón y colóquelo como el primer elemento de la nueva lista.
• Apile la lista restante.
• Extraiga el primer elemento del nuevo montón y colóquelo como el siguiente elemento de la nueva lista.
• Repita los pasos anteriores en orden hasta que la lista del montón esté vacía. Al final, la nueva lista está ordenada.

Complejidad de tiempo Heapsort adecuada

El enfoque de una etapa se utiliza para determinar la complejidad del tiempo para heapsort. Suponga que hay 8 elementos sin ordenar para ordenar.

El número máximo posible de operaciones es:

El promedio de estos números de operaciones es:

Observe que los últimos cuatro montones de la ilustración anterior no cambiaron cuando se eliminó el primer elemento. Algunos de los montones anteriores tampoco cambiaron cuando se eliminó el primer elemento. Con eso, un mejor número medio de operaciones principales (permutas) es 3 y no 4,5. Entonces, un mejor número promedio total de operaciones principales es:

desde registro ₂ 8 = 3.

En general, la complejidad de tiempo de caso promedio para heapsort es:

Donde el punto significa multiplicación y n es N, el número total de elementos en la lista (cualquier lista).

Nótese que se ha ignorado la operación de extraer el primer elemento. En el tema de la complejidad del tiempo, se ignoran las operaciones que toman tiempos relativamente cortos.

Codificando en C++

En la biblioteca de algoritmos de C++, hay una función make_heap(). La sintaxis es:

Toma el iterador que apunta al primer elemento de un vector como su primer argumento y luego el iterador que apunta justo más allá del final del vector como su último argumento. Para la lista desordenada anterior, la sintaxis se usaría de la siguiente manera para obtener un montón mínimo:

Este código cambia el contenido de un vector a una configuración de almacenamiento dinámico mínimo. En los siguientes vectores de C++, se utilizarán dos vectores en lugar de dos matrices.

Para copiar y devolver el primer elemento de un vector, use la sintaxis del vector:

Para eliminar el primer elemento de un vector y tirarlo, use la sintaxis del vector:

Para agregar un elemento en la parte posterior de un vector (siguiente elemento), use la sintaxis del vector:

El comienzo del programa es:

Las bibliotecas de algoritmos y vectores están incluidas. Lo siguiente en el programa es la función heapsort(), que es:

Es una función recursiva. Utiliza la función make_heap() de la biblioteca de algoritmos de C++. El segundo segmento de código en la definición de la función extrae el primer elemento del vector anterior después de la creación del montón y lo agrega como el siguiente elemento para el nuevo vector. Tenga en cuenta que en la definición de la función, los parámetros del vector son referencias, mientras que la función se llama con los identificadores (nombres).

Una función principal de C++ adecuada para esto es:

La salida es:

ordenado (completamente).

Conclusión

El artículo discutió en detalle la naturaleza y la función de Heap Sort, comúnmente conocido como Heapsort, como un algoritmo de clasificación. La complejidad del tiempo de Heapify, la ilustración de Heapsort y Heapsort como algoritmo se cubrieron y respaldaron con ejemplos. La complejidad de tiempo promedio para un programa heapsort bien escrito es O(nlog(n))