Amare la complejidad del tiempo y el lenguaje C
El montón mínimo anterior describe un montón donde el número de niños por nodo principal puede ser más de dos. Un montón binario es uno en el que el mayor número de hijos por nodo principal es dos. Un montón binario completo es uno en el que cada nodo tiene dos hijos, con la excepción de que, en el nivel más bajo, puede haber solo un nodo de hoja sin un hermano; con el resto de los nodos de hoja más bajos emparejados y comenzando desde el extremo extremo izquierdo de la última fila, terminando con este nodo de hoja individual, que debe ser un nodo izquierdo.
Amarificar significa construir (crear) un montón. Dado que un árbol donde cada nodo puede tener cualquier número de niños puede convertirse en un árbol binario completo, el verdadero objetivo de este artículo es producir la complejidad del tiempo para acumular un árbol binario completo.
Un diagrama de ejemplo de un árbol binario completo es:
Cualquier nodo de hoja en el nivel más bajo que no tenga un hermano tiene que ser un nodo izquierdo. Todos los nodos de la última fila, incluido un posible nodo izquierdo, están "sonrojados" al extremo izquierdo de la última fila.
Por la definición de un montón, un hermano izquierdo puede ser más pequeño, mayor o igual al hermano derecho. El orden de ambos hermanos no se especifica.
Árbol binario completo
El árbol anterior es un árbol binario completo, pero no es un árbol binario completo. También es un montón mínimo. Si fuera un árbol binario completo, entonces todos los nodos del último pero uno habrían tenido dos hijos cada uno. El árbol anterior se vuelve a dibujar a continuación como un árbol binario completo:
Un árbol puede ser representado por una matriz. El árbol se lee de arriba a abajo, de izquierda a derecha, fila por fila; luego colocado en la matriz. La siguiente tabla muestra la matriz de contenido e índices para este árbol:
| 4 | 6 | 12 | 8 | 7 | dieciséis | 15 | 23 | 10 | 20 | 18 | 25 | nulo | nulo | nulo |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
Los valores de la celda están en la primera fila de tabla. Los índices basados en cero están en la segunda fila de tabla.
Relación entre un índice de padres y sus hijos índices
En el árbol o la matriz correspondiente, la raíz está en el índice 0 para la indexación basada en cero. Que yo sea la variable que mantenga cada índice. Los hijos de la raíz están en los índices 1 y 2, que son 0 + 1 y 0 + 2. Los hijos del nodo 1 están en los índices 3 y 4, que son 1 + 2 y 1 + 3. Los hijos del nodo 2 están en el índice 5 y 6, que son 2 + 3 y 2 + 4. Los hijos del nodo 3 están en el índice 7 y 8, que son 3 + 4 y 3 + 5. Los hijos del nodo 4 están en el índice 9 y 10, que son 4 + 5 y 4 + 6; etcétera.
Que yo sea el índice de padres por ahora. Entonces los hijos de cada padre están en el índice i + i + 1 y en i + i + 2, que son:
2i +1 y 2i +2
El reverso debe ser conocido. Es decir, dado un índice, yo para un hijo izquierdo o niño derecho, ¿cuál es el índice de los padres?? Para el niño izquierdo en el índice 1 y el niño derecho en el índice 2, el padre está en el índice 0. Para el niño izquierdo en el índice 3 y el niño derecho en el índice 4, el padre está en el índice 1. Para el niño izquierdo en el índice 5 y el niño derecho en el índice 6, el padre está en el índice 2. Para el niño izquierdo en el índice 7 y el niño derecho en el índice 8, el padre está en el índice 3. Para el niño izquierdo en el índice 9 y el niño derecho en el índice 10, el padre está en el índice 4.
Esta vez, es un índice infantil (no un índice de padres). Entonces, el padre de cada niño izquierdo está en el índice I/2 de la división entera, y el padre del niño derecho, que es el mismo que el padre del niño izquierdo (hermano), está en el resultado entero de (i-1) /2, yo.mi.:
I/2 y (I-1)/2
donde la división es división entera.
También es bueno saber si un nodo es un niño izquierdo o un niño derecho: si la división normal por 2 tiene un resto, entonces ese es un nodo izquierdo por indexación basada en cero. Si la división normal por 2 no tiene ningún resto, entonces ese es un nodo correcto por indexación basada en cero.
El código en C, para saber si el nodo secundario es un nodo izquierdo o un nodo derecho, es:
if (i%2 == 0)
// El nodo es un nodo derecho
demás
// El nodo es el nodo izquierdo
Después de saber que un nodo es un nodo izquierdo, el índice principal se puede obtener como un resultado entero de i/2. Después de saber que un nodo es un nodo correcto, el índice principal se puede obtener como un resultado entero de (I-1)/2.
Altura de un montón binario completo y algunos índices
Número total de nodos
Aviso desde el último diagrama completo por encima de que cuando el nivel de un montón aumenta en 1, su número total de nodos se duplica aproximadamente. Precisamente, el siguiente nivel viene con la cantidad de nodos que hace que el nuevo total, la suma de todos los nodos anteriores, más 1, tiempos 2, luego menos 1. Cuando la altura es 1, hay 1 nodo = (0 + 1) x 2 - 1 = 2 - 1 = 21 - 1. Cuando la altura es 2, hay 3 nodos = (1 + 1) x 2 - 1 = 4 - 1 = 22 - 1. Cuando la altura es 3, hay 7 nodos = (3 + 1) x 2 - 1 = 8 - 1 = 23 - 1. Cuando la altura es 4, hay 15 nodos = (7 + 1) x 2 - 1 = 16 - 1 = 24 - 1. Cuando la altura es 5, hay 31 nodos = (15 + 1) x 2 - 1 = 32 - 1 = 25 - 1. Cuando la altura es 6, hay 63 nodos = (31 + 1) x 2 - 1 = 64 - 1 = 26 - 1. Cuando la altura es 7, hay 127 nodos = (63 + 1) x 2 - 1 = 128 - 1 = 27 - 1; etcétera.
En general, cuando la altura es H,
No. de nodos = 2h - 1
Índice de nodo Último
Para un árbol binario y para la indexación basada en cero, el último índice es:
Último índice = n - 1
donde n es el número total de nodos, o simplemente el número de nodos.
Número de nodos sin última fila
Para un árbol binario completo, dos veces el número de nodos para la última fila da el número total de nodos menos 1. Visto de otra manera, el número de nodos para la última fila es igual al número de todos los nodos anteriores, tiempos dos, más 1. Entonces, el número de nodos sin la última fila es:
No. de nodos sin último = resultado entero de n/2
Esto se debe a que, para la indexación basada en cero, el número total de nodos para un árbol binario completo es siempre un número impar. Por ejemplo: si el número de nodos (total) es 15, entonces 15/2 = 7½. Se toma el resultado entero, 7, y la mitad se tira. Y 7 es el número de nodos sin la última fila; ver arriba.
Índice para el primer nodo de la última fila
Se debe conocer el índice para el primer nodo de la última fila. Para la indexación basada en cero, donde el primer nodo (elemento) está en el índice 0, el índice para el primer nodo de la última fila es el número de nodos para todos los nodos sin la última fila. Es:
Resultado entero de N/2
Tenga en cuenta que en la matriz correspondiente, los nodos del árbol se llaman elementos.
Tamizar y tamizar
Considere el siguiente sub-árbol de tres nodos:
Por la propiedad mínima del montón, el nodo principal debe ser más pequeño o igual que los nodos más pequeños de los niños. Entonces, el nodo C tiene que ser cambiado con los menores nodos de los niños; No importa si lo menos es el hermano izquierdo o derecho. Esto significa que C tiene que ser intercambiado con A para tener:
A medida que "A" se sube para tomar el lugar de C, eso es tamizar. A medida que C se mueve hacia abajo para tomar el lugar de A, eso es tamizar hacia abajo.
Ilustración de acumulación
El montón, como se muestra arriba, es un pedido parcial, desde el valor más pequeño hasta el valor más grande. No es un pedido exhaustivo (no clasifica). Como se expresó anteriormente, el montón puede estar en forma de árbol o en forma de matriz. Como se expresó anteriormente, la acumulación ya ha tenido lugar. En la práctica, el programador no necesariamente encontrará un árbol ya calmado. Encontraría una lista que está completamente en desorden (completamente sin clasificar). Esta lista desordenada puede existir en forma de árbol o en forma de matriz. El siguiente es un árbol desordenado (sin clasificar) y su matriz correspondiente:
La matriz correspondiente es:
| 10 | 20 | 25 | 6 | 4 | 12 | 15 | 23 | 8 | 7 | 18 | dieciséis | nulo | nulo | nulo |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
El árbol se lee fila por fila, de izquierda a derecha y de arriba a abajo, mientras se coloca en las celdas de la matriz. Deje que el nombre de la matriz sea ARR y deje que la variable que represente el índice basado en cero sea I. En este artículo, la raíz está en el índice 0.
Este árbol se someterá a pedidos parciales para convertirse en un montón mínimo. Cuando se complete el pedido parcial, será el montón mínimo dado en la sección Introducción de este artículo. En esta sección, el orden parcial se realiza manualmente.
Para simplificar el montón (proceso de pedido parcial), el árbol binario no ordenado completo debe hacerse un árbol binario completo antes de ser procesado. Para que sea un árbol binario completo, agregue elementos cuyos valores son mayores que el valor más alto que ya se encuentra en el montón desordenado. En este artículo, esto se hará con la matriz y no con la forma gráfica del árbol.
El elemento más alto (nodo) es 25. Deje que los tres números agregados para hacer que un árbol completo sea: 26, 27 y 28. La matriz correspondiente para el árbol completo se convierte en:
| 10 | 20 | 25 | 6 | 4 | 12 | 15 | 23 | 8 | 7 | 18 | dieciséis | 26 | 27 | 28 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
Cuando la lista no ordenada se ordena parcialmente por la definición del montón, los últimos tres elementos permanecerán en sus últimas posiciones; y puede ser fácilmente abandonado.
Cuando esta lista desordenada está parcialmente ordenada por la definición del montón, sería la lista parcialmente ordenada dada anteriormente (Introducción). Una lista parcialmente ordenada tiene alguna clasificación, pero no es un pedido completo (no es una clasificación completa).
Reordenamiento manual (edificio de montón)
La matriz desordenada se puede colocar así:
10 20 25 06 04 12 15 23 08 07 18 16 26 27 28
Hay 15 elementos. El resultado entero de 15/2 es 7. La lista debe dividirse en dos mitades, con la primera mitad de 7 y la segunda mitad, 8, como sigue:
10 20 25 06 04 12 15 | 23 08 07 18 16 26 27 28
Esta división puede considerarse como una operación principal. La construcción de Heap continúa desde el extremo derecho con los pares de elementos, 27 y 28, identificados como niños de 15. 15 es menos de 27 o 28. Por lo tanto, este sub-árbol de tres nodos satisface la propiedad mínima del montón, y los nodos no se tocan por ahora. Esta verificación puede considerarse otra operación principal. Por lo tanto, hay dos operaciones principales hasta ahora (una división de matriz y un cheque).
16 y 26 son niños de 12. 12 es menos de 16 o 26. Por lo tanto, este sub-árbol de tres nodos satisface la propiedad mínima del montón, y los nodos no se tocan (por ahora). Esta verificación puede considerarse otra operación principal. Por lo tanto, hay tres operaciones principales hasta ahora (una división y dos cheques).
07 y 18 son los hijos de 04. 04 es inferior a 07 o 18. Por lo tanto, este sub-árbol de tres nodos satisface la propiedad mínima del montón, y los nodos no se tocan (por ahora). Esta verificación puede considerarse otra operación principal. Por lo tanto, hay cuatro operaciones principales hasta ahora (una división y tres cheques).
23 y 08 son los hijos de 06. 06 es menos de 23 o 08. Por lo tanto, este sub-árbol de tres nodos satisface la propiedad mínima del montón, y los nodos no se tocan (por ahora). Esta verificación puede considerarse otra operación principal. Por lo tanto, hay cinco operaciones principales hasta ahora (una división y cuatro cheques).
Los 8 elementos de la última fila del árbol y sus padres han sido revisados. Para ir al nivel anterior, la parte izquierda del árbol debe dividirse por 2, y se toma el resultado entero. El resultado entero de 7/2 es 3. La nueva colocación de la lista es:
10 20 25 | 06 04 12 15 | 23 08 07 18 16 26 27 28
Esta división puede considerarse como una operación principal. Por lo tanto, hay seis operaciones principales hasta ahora (dos divisiones y cuatro cheques).
12 y 15 son niños de 25. 25 es mayor que 12 o 15. Este sub-árbol de tres nodos no satisface la propiedad mínima del montón, por lo que los nodos deben tocarse. Sin embargo, esta verificación aún puede considerarse otra operación principal. Por lo tanto, hay siete operaciones principales hasta ahora (dos divisiones y cinco cheques).
Tamizar hacia abajo tiene que tener lugar y posiblemente hasta la última fila. Cada tamiz (intercambio) es la operación principal.
25 se intercambia con el menor de sus hijos, 12 para dar la configuración:
10 20 12 | 06 04 25 15 | 23 08 07 18 16 26 27 28
25 está ahora en el tercer nivel y ya no en el segundo nivel. 25 es ahora el padre de 16 y 26. En este punto, 25 es mayor que 16 pero menos de 26. Entonces 25 y 16 están cambiados. Este intercambio es otra operación principal, por lo que hasta ahora hay nueve operaciones principales (dos divisiones, cinco cheques y dos intercambios). La nueva configuración es:
10 20 12 | 06 04 16 15 | 23 08 07 18 25 26 27 28
En el segundo nivel de la lista dada, había 20 y 25. 25 se han tamizado hasta la última fila. 20 todavía está por verificar.
Actualmente, 06 y 04 son niños de 20. 20 es mayor que 06 o 04. Este sub-árbol de tres nodos no satisface la propiedad mínima del montón, por lo que los nodos deben tocarse. Sin embargo, esta verificación aún puede considerarse otra operación principal. Por lo tanto, hasta ahora hay diez operaciones principales (dos divisiones, seis cheques y dos intercambios). Tamizar hacia abajo tiene que tener lugar y posiblemente hasta la última fila. Cada tamiz (intercambio) es la operación principal.
20 se intercambia con el menor de sus hijos, 04 para dar la configuración:
10 04 12 | 06 20 16 15 | 23 08 07 18 25 26 27 28
20 está ahora en el tercer nivel y ya no está en el segundo nivel. 20 es ahora el padre de 07 y 18. En este punto, 20 es mayor que 07 o 18. Entonces 20 y 07 están cambiados. Este intercambio es otra operación principal, por lo que hasta ahora hay doce operaciones principales (dos divisiones, seis cheques y cuatro intercambios). La nueva configuración es:
10 04 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
Los tope hacia abajo del camino anterior han terminado. La parte izquierda que no se ha verificado por completo debe dividirse en dos (ir al nivel anterior) para tener:
10 | 04 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
El resultado entero de 3/2 es 1.
Actualmente, 04 y 12 son niños de 10. 10 es mayor que 04 pero menos de 12. Este sub-árbol de tres nodos no satisface la propiedad mínima del montón, por lo que los nodos deben tocarse. Sin embargo, esta verificación aún debe considerarse como otra operación principal. Por lo tanto, hay catorce operaciones principales hasta ahora (tres divisiones, siete cheques y cuatro swaps). Tamizar hacia abajo tiene que tener lugar y posiblemente hasta la última fila. Cada tamiz (intercambio) es la operación principal.
10 se intercambia con el menor de sus hijos, 04 para dar la configuración:
04 | 10 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
10 está ahora en el segundo nivel y ya no está en el primer nivel. 10 es ahora el padre 06 y 07. En este punto, 10 es mayor que 06 o 07. Entonces se intercambian 10 y 06. Este intercambio es otra operación principal, por lo que hasta ahora hay dieciséis operaciones principales (tres divisiones, siete cheques y seis intercambios). La nueva configuración es:
04 | 06 12 | 10 07 16 15 | 23 08 20 18 25 26 27 28
10 está ahora en el tercer nivel y ya no en el segundo nivel. 10 es ahora el padre 23 y 08. En este punto, 10 es menos de 23 pero mayor que 08. Entonces 10 y 08 están cambiados. Este intercambio es otra operación principal, por lo que hasta ahora hay diecisiete operaciones principales (tres divisiones, siete cheques y siete intercambios). La nueva configuración es:
04 | 06 12 | 08 07 16 15 | 23 10 20 18 25 26 27 28
Bueno, la corriente, la división y el intercambio comenzaron en el último índice y ha alcanzado el primer índice, con todas las consecuencias de los tamizos a la baja. Esto significa que la construcción del montón está completo y, en este caso, con diecisiete operaciones principales (tres divisiones, siete cheques y siete intercambios). Hubo 15 elementos, aunque los últimos tres fueron elementos ficticios necesarios para simplificar el edificio del montón.
Algoritmo
Hay diferentes algoritmos para la construcción del montón. La ilustración dada anteriormente será la más eficiente si un valor de los padres se intercambia con cualquiera de los niños que son cada vez menos de los niños. Los pasos para el algoritmo son:
- Divide el número entero de elementos por dos.
- Continúe desde la mitad derecha, revisando un par de hermanos con el padre y intercambiando si es necesario.
- Cuando se hayan verificado todos los nodos del último nivel, con posible intercambio, continúe al nivel anterior y repita los dos pasos anteriores. El intercambio es tamizado, y esto puede tener que alcanzar el nivel más bajo.
- Cuando la raíz haya sido revisada y posiblemente intercambiada, detente.
Complejidad del tiempo
La complejidad del tiempo es el tiempo de ejecución relativo de algún código. En este caso, es el tiempo de ejecución relativo del proceso de construcción del montón. La complejidad del tiempo es en realidad el número de operaciones principales en el código (programa).
Oficialmente, se dice que la complejidad del tiempo del algoritmo para este artículo es N operaciones, donde n es el número de elementos en la matriz desordenada más los elementos ficticios. En este caso, n es 15. Entonces, la complejidad del tiempo para este algoritmo es 15.
¿Por qué debería ser 15 en lugar de 17?? Es decir, ¿por qué debería ser n?? - Bueno, dado que la división no es partición, la duración de cada acción de división es pequeña y puede ser descuidada. Con eso y para la ilustración anterior, el número de operaciones principales se convertirá en 14 (siete cheques y siete intercambios), con las 3 divisiones ignoradas.
Además, si el valor de un padre se cambia con cualquiera de los niños que son menos, y no siempre el menor de los niños, entonces el tiempo de verificación general se reducirá. Esto hará que el tiempo de control sea pequeño e ignorado. Con eso y para la ilustración anterior, el número de operaciones principales se convertirá en 7 (siete swaps), con las 3 divisiones ignoradas y los siete cheques también ignorados.
Nota: Para un buen programa de construcción de montón, solo las operaciones de intercambio (tamizos en este caso) se consideran en complejidad del tiempo. En este caso, hay 7 operaciones y no 15. Al tratar con la complejidad del tiempo, el número máximo posible de operaciones es lo que se debe dar.
Es posible que se intercambien los 15 nodos anteriores. Entonces, la complejidad del tiempo para este ejemplo debe administrarse como 15 y no 7.
La complejidad del tiempo para este algoritmo se da, en términos generales, como:
En)
Donde n es n, esta es la notación Big-O. Esta notación usa mayúsculas y sus paréntesis. Dentro de los paréntesis es la expresión del posible número máximo de operaciones para que el código (programa) complete.
Codificación en C
La función principal C para acumular la matriz indordenada anteriormente es:
int main (int argc, char ** argv)
int n1 = 12;
int a1 [] = 10, 20, 25, 6, 4, 12, 15, 23, 8, 7, 18, 16;
int a2 [] = 10, 20, 25, 6, 4, 12, 15, 23, 8, 7, 18, 16, 26, 27, 28;
BuildHeap (A2, N2);
for (int i = 0; i = arr [leftindx] && arr [leftindx]> = arr [rightIndx])
int temp = arr [parentIndx]; arr [parentIndx] = arr [rightIndx]; arr [rightIndx] = temp;
lastdown = rightIndx;
else if (arr [parentIndx]> = arr [rightIndx] && arr [rightIndx]> = arr [leftindx])
int temp = arr [parentIndx]; arr [parentIndx] = arr [leftIndx]; arr [leftindx] = temp;
Lastdown = LeftIndx;
else if (arr [parentIndx]> = arr [rightIndx] && arr [rightIndx] = arr [leftindx] && arr [leftindx] <= arr[rightIndx])
int temp = arr [parentIndx]; arr [parentIndx] = arr [leftIndx]; arr [leftindx] = temp;
Lastdown = LeftIndx;
regresar Lastdown;
Hay una función de tamizado. Usaría la función swap () y tamizaría directamente al nivel más bajo en una ruta. Es:
int nextindx;
nulo siftdown (int arr [], int n2, int i)
int LeftIndx, RightIndx;
int parentindx = i;
LeftIndx = 2*i+1;
RightIndx = 2*i+2;
if (parentIndx = 0)
nextIndx = swap (arr, parentIndx, leftIndx, rightIndx);
if (nextIndx = halfindx/2; i--)
Siftdown (A2, N2, I);
N = n/2;
if (n> = 1)
Buildheap (A2, N);
Todos los segmentos de código anteriores se pueden ensamblar para formar un programa que acumule la matriz no ordenada.
Conclusión
El algoritmo más eficiente para la complejidad del tiempo de la acumulación es:
En)