¿Por qué un montón de tamaño n tiene altura de piso (log (n))?

Max nodos en un árbol completo de altura h
[matemáticas] 2 ^ {h + 1} – 1 [/ matemáticas]

Max nodos en un árbol completo de altura h-1
[matemáticas] 2 ^ {h} – 1 [/ matemáticas]

Número mínimo de nodos en un árbol de altura h
[matemáticas] 2 ^ {h} – 1 + 1 [/ matemáticas]

Esto implica que
[matemáticas] 2 ^ {h} <= n <2 ^ {h + 1} [/ matemáticas]
[matemáticas] h <= lg (n) Como h es un número entero, se deduce que h = floor (lg (n))

La altura de un montón es la distancia del nodo raíz desde el nodo más alejado (o nodos) en el montón. Ahora la distancia se puede calcular moviéndose desde el último elemento ([matemática] nth) [/ matemática] que estará entre el más alejado y contando el número de bordes en el camino. También tenga en cuenta que solo nos interesan las posiciones de los nodos (que son enteros puros) en cada paso.

Entonces, en el montón anterior [matemática] n = 10 [/ matemática]. Para llegar al nodo raíz en [matemática] 1 [/ matemática] dividimos repetidamente entre [matemática] 2 [/ matemática] (para llegar al padre) hasta llegamos a [matemáticas] 1 [/ matemáticas] que es: [matemáticas] 10 → 5 → 2 → 1 [/ matemáticas]. Puede ver que solo estamos interesados ​​en valores enteros de la operación de división. ¿Por qué? Como no puede decir que un elemento está en [matemáticas] 5/2 = 2.5 [/ matemáticas] en la posición, debe ser un número entero.

Ahora, el número de veces que tiene que realizar la división es la potencia a la que se puede aumentar [matemática] 2 [/ matemática] para producir [matemática] n [/ matemática] es decir => logaritmo a la base [matemática] 2 [/ matemáticas] de [matemáticas] n [/ matemáticas] o simplemente [matemáticas] lg (n). [/ matemáticas]

Dado [matemáticas] n = 10: lg (10) = 3.3219280948873626 [/ matemáticas].

Es un hecho que todos los números no son perfectamente divisibles por [math] 2 [/ math], lo que le da valores no enteros en la división o en el registro. Entonces, ¿qué hacemos ahora?

Vamos a pensar en redondear el valor al siguiente entero posible: es decir, hacer [matemática] ceil (lg (10)) = 4 [/ matemática] pero esto es mayor que el número de pasos dados para llegar a la raíz, que es solo [matemáticas] 3 [/ matemáticas] operaciones de división. Entonces hacer [math] floor (lg (10)) = 3 [/ math] te da el número exacto de pasos dados para llegar al nodo raíz.

Suponiendo que está hablando de un montón binario. Son tres binarios completamente formados, por lo tanto, si imagina uno que contiene 7 elementos, tendrá un elemento en la raíz. dos elementos en el primer nivel y 4 elementos en el tercero.

Entonces para derivar la fórmula:
2 ^ h = hojas (las dos provienen de ser binarias)
Si resolvemos para n obtenemos:
n = 2 ^ (h + 1) – 1
Para poder resolver la altura, debemos aplicar log2 y limpiarlo.
log2 (n + 1) – 1 = h