Complejidad del tiempo del montón

Sort de montón, escrito como Heapsort, es una especie de algoritmo de clasificación. Se necesita una lista que se ordene parcialmente y produce una lista ordenada de ella. La clasificación puede ser ascendente o descendente. En este artículo, la clasificación es ascendente. Tenga en cuenta que HeApsort no clasifica una lista incompleta de. Clasifica una lista parcialmente ordenada (ordenada). Esa lista parcialmente ordenada es un montón. En este artículo, el montón considerado es el montón mínimo (ascendente).

Se conoce un montón como "parcialmente ordenado" y no "parcialmente ordenado". La palabra "ordenar" significa ordenado completo (clasificación completa). Un montón no se ordena parcialmente arbitrariamente. Se ordena parcialmente un montón después de un criterio (patrón), como se muestra a continuación.

Entonces, el montón consta de dos etapas: construir el montón y extraer el elemento ordenado desde 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 desde una construcción anterior, donde se ha eliminado un elemento. Y con eso, Heapsort clasifica una lista completamente sin clasificar.

El objetivo de este artículo es explicar brevemente el montón y luego producir su complejidad de tiempo (ver el significado de la complejidad del 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 max-heap es uno 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 mínimo es uno en el que el primer elemento es el elemento menor, y toda la lista se ordena parcialmente 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 llama nodo.

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

9	19	24	5	3	11	14	22	7	6	17	15	nulo	nulo	nulo
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

La primera fila de esta tabla son los elementos de la matriz. En la segunda fila están los índices basados ​​en cero. Esta lista de elementos se puede expresar como un árbol. Se han agregado los elementos nulos para hacer un árbol binario completo. Estrictamente hablando, los elementos nulos no son parte de la lista (árbol). Esta lista no tiene pedido, por lo que aún no es un montón. Se convertirá en un montón cuando haya tenido pedidos parciales, 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 elementos en orden parcial de acuerdo con la propiedad MIN-HeAP. El orden parcial puede verse como un tipo parcial (aunque la palabra "ordenar" significa orden completo).

Si un árbol binario es un montón o no, cada padre tiene dos hijos, excepto los nodos de la hoja. Existe una relación matemática entre los índices entre cada padre y sus hijos. Es el siguiente: si el padre está en el índice I, entonces el niño izquierdo está en el índice:

2*i + 1

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

2*i + 2

Esto es para 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 a 2 × 0+2 = 2. Un padre en el índice 1 tiene su hijo izquierdo en el índice 2 × 1+1 = 3 y el niño derecho en el índice 2 × 1+2 = 4; etcétera.

Por la propiedad Min-HeAP, un padre en I es menor o igual al niño izquierdo a 2i+1 y menos o igual al niño derecho a 2i+2.

Montón

Manifique 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 el árbol es un montón.

Si la lista anterior no armada se calma, se convertirá en:

3	5	11	7	6	15	14	22	9	19	17	24	nulo	nulo	nulo
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

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 tuvieron que ser revisados ​​y algunos intercambiados.

Observe que el elemento más pequeño y del primer es 3. El resto de los elementos siguen de manera ascendente pero ondulante. Si los niños izquierdo y derecho en las posiciones 2i+1 y 2i+2 son mayores o iguales a los padres en i, entonces este es un mínimo de madera. Esto no es un pedido o clasificación completa. Este es un pedido parcial, de acuerdo con la propiedad del montón. Es desde aquí que comienza la siguiente etapa para el montón.

Pleapify Time Complejidad

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 ese código complete. Hay diferentes algoritmos para la construcción del montón. El más eficiente y más rápido divide continuamente la lista por dos, verificando los elementos desde el fondo y luego haciendo algún intercambio de elementos. Sea n el número de elementos prácticos en la lista. Con este algoritmo, el número máximo de operaciones principales (intercambio) es n. La complejidad del tiempo para la acumulación se da anteriormente como:

En)

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

Recuerde: la adición puede convertirse en multiplicación si lo mismo se agrega se repite.

Ilustración de Heapsort

La lista anterior sin clasificar se utilizará para ilustrar HeApsort. La lista dada es:

9 19 24 5 3 11 14 22 7 6 17 15

El mínimo de la lista producido de la lista es:

3 5 11 7 6 15 14 22 9 19 17 24

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 menor, que es el primer elemento, del montón, volviendo a capacitar el montón restante y eliminar los elementos menos en los resultados. El elemento menor es siempre el primer elemento en el montón de reapimidad. Los elementos no se eliminan y 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 se ordenó parcialmente.

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

3

y

5 11 7 6 15 14 22 9 19 17 24

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

5 6 7 9 15 14 22 11 19 17 24

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

3 5

y

6 7 9 15 14 22 11 19 17 24

Amarar el conjunto restante daría:

6 7 9 15 14 22 11 19 17 24

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

3 5 6

y

7 9 15 14 22 11 19 17 24

Amarar el conjunto restante daría:

7 9 11 14 22 15 19 17 24

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

3 5 6 7

y

9 11 14 22 15 19 17 24

Activar el conjunto restante da:

9 11 14 22 15 19 17 24

Extraer 9 y agregar a la nueva lista, ofrece los resultados:

3 5 6 7 9

y

11 14 22 15 19 17 24

Activar el conjunto restante da:

11 14 17 15 19 22 24

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

3 5 6 7 9 11

y

14 17 15 19 22 24

Amarar el conjunto restante daría:

14 17 15 19 22 24

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

3 5 6 7 9 11 14

y

17 15 19 22 24

Amarar el conjunto restante daría:

15 17 19 22 24

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

3 5 6 7 9 11 14 15

y

17 19 22 24

Amarar el conjunto restante daría:

17 19 22 24

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

3 5 6 7 9 11 14 15 17

y

19 22 24

Amarar el conjunto restante daría:

19 22 24

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

3 5 6 7 9 11 14 15 17 19

y

22 24

Activar el conjunto restante da:

22 24

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

3 5 6 7 9 11 14 15 17 19 22

y

24

Activar el conjunto restante da:

24

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

3 5 6 7 9 11 14 15 17 19 22 24

y

- - -

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

Algoritmo de montón

Aunque el lector podría haber leído en los libros de texto que Heapsort consta de dos etapas, HeapSort puede verse como una etapa, que se reduce iterativamente de la matriz dada. Con eso, el algoritmo para clasificar con HeApsort es el siguiente:

• Aleapifique la lista sin clasificar.
• Extraiga el primer elemento del montón y lo póngalo como el primer elemento de la nueva lista.
• Atepifique la lista restante.
• Extraiga el primer elemento del nuevo montón y coloque como el siguiente elemento de la nueva lista.
• Repita los pasos anteriores en orden hasta que la lista de montón esté vacía. Al final, la nueva lista está ordenada.

Pleapsort complejidad de tiempo apropiado

El enfoque de una etapa se utiliza para determinar la complejidad del tiempo para el montón. Suponga que hay 8 elementos sin clasificar.

El posible número máximo de operaciones para acumular los 8 elementos es 8.
El posible número máximo de operaciones para acumular los 7 elementos restantes es 7.
El posible número máximo de operaciones para acumular los 6 elementos restantes es 6.
El posible número máximo de operaciones para acumular los 5 elementos restantes es 5.
El posible número máximo de operaciones para acumular los 4 elementos restantes es 4.
El posible número máximo de operaciones para acumular los 3 elementos restantes es 3.
El posible número máximo de operaciones para acumular los 2 elementos restantes es 2.
El posible número máximo de operaciones para acumular el elemento 1 restante es 1.

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

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

El promedio de estos números de operaciones es:

36/8 = 4.5

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

24 = 8 x 3
=> 24 = 8 x log₂8

Desde el registro₂8 = 3.

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

En.log2n)

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

Tenga en cuenta que se ha ignorado la operación de extraer el primer elemento. Sobre el tema de la complejidad del tiempo, se ignoran las operaciones que toman tiempos relativamente cortos.

Codificación en C++

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

plantilla
constexpr void make_heap (randomAccessIterator First, randomAccessIterator Last, Compare Comp);

Toma el iterador señalando el primer elemento de un vector como su primer argumento y luego el iterador apuntando más allá del final del vector como su último argumento. Para la lista no organizada anterior, la sintaxis se utilizaría de la siguiente manera para obtener un montón mínimo:

vector vtr = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vector:: iterator iterb = vtr.comenzar();
vector:: iterator ITere = VTR.fin();
make_heap (Iterb, Itere, Greater());

Este código cambia un contenido vectorial en una configuración mínima de montón. En los siguientes vectores 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:

Constexpr Reference Front ();

Para eliminar el primer elemento de un vector y tírelo, use la sintaxis del vector:

ERASE DE CONSTEXPR ITERATOR (posición const_iterator)

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

constexpr void push_back (const t & x);

El comienzo del programa es:

#incluir
#incluir
#incluir
usando el espacio de nombres STD;

Se incluyen el algoritmo y las bibliotecas vectoriales. Lo siguiente en el programa es la función HeepSort (), que es:

Vacío del montón (vector & Oldv, vector & newv)
Si (Oldv.size ()> 0)
vector:: iterator iterb = Oldv.comenzar();
vector:: iterator iterere = Oldv.fin();
make_heap (Iterb, Itere, Greater());
int next = Oldv.frente();
viejo.borrar (iterb);
nuevo.push_back (siguiente);
Heapsort (Oldv, NewV);

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

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

int main (int argc, char ** argv)

vector Oldv = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vector newv;
Heapsort (Oldv, NewV);
para (int i = 0; icout << newV[i] << ";

cout << endl;
regresar 0;

La salida es:

3 5 6 7 9 11 14 15 17 19 22 24

Ordenado (completamente).

Conclusión

El artículo discutido en detalle la naturaleza y la función del tipo de montón comúnmente conocido como Heapsort, como algoritmo de clasificación. La complejidad del tiempo de los amenazos, la ilustración de HeepSort y el montón como un algoritmo fueron cubiertos y respaldados por ejemplos. La complejidad promedio de tiempo para un programa de Heapsort bien escrito es O (NLOG (N))