Suponiendo que el peor de los casos ocurre cuando el último nivel está medio lleno (lo que justificaré más adelante), responderé primero a la segunda pregunta. Supongamos que hay k nodos en el segundo último nivel. entonces k / 2 de ellos tendrán hojas. Así, [matemáticas] número de hojas en el último nivel = número de nodos en el segundo último nivel [/ matemáticas]. Considere dos subárboles enraizados en el nodo izquierdo y derecho de la raíz. Ambos tienen k / 2 nodos en el segundo último nivel (las hojas surgen del izquierdo pero no del derecho). Por lo tanto, el número total de nodos en cada subárbol (excluyendo las hojas en el último nivel para el subárbol izquierdo) será [matemática] 2 * k / 2-1 = k-1 [/ matemática] (Este es un resultado muy fácil para demostrar que número total de nodos en un árbol binario completamente lleno = (2 * número de nodos en el último nivel) -1, utiliza la suma simple de una progresión geométrica). Ahora todo el montón consta de cuatro porciones:
a) dejó el subárbol sin las hojas en el último nivel (k-1)
b) subárbol derecho (k-1)
c) raíz
d) deja en el último nivel (k)
Así
[mates]
k-1 + k-1 + k + 1 = n [/ matemáticas]
[matemáticas] 3k = n-1 [/ matemáticas]
Ahora, el peor de los casos ocurre cuando el heapify máximo se ejecuta en la raíz y luego avanza hacia las hojas en el último nivel. Por lo tanto, el número total de nodos cubiertos [matemática] = (k + 1 + k-1) \ aprox (2 * n / 3) [/ matemática].
Ahora respondemos a la primera pregunta de por qué este es el peor de los casos. La razón es que supones que tienes más de la mitad en la última fila del árbol. Entonces los tres componentes que dijimos que eran casi iguales (subárbol izquierdo sin hojas, subárbol derecho, hojas en el último nivel) no serán iguales. El último componente sería más grande. Debido a esto, su subárbol izquierdo (incluidas las hojas en el último nivel) sería [matemática] <(2 * n / 3) [/ matemática] ya que parte de esta fracción se extiende en las hojas del subárbol derecho en el último nivel .
PD: Lo siento, soy nuevo en Quora, por lo que un mal diseño.
- ¿Se puede implementar una lista vinculada individualmente como una lista doblemente vinculada?
- ¿Cómo se utilizan los punteros para la asignación dinámica de memoria de las variables?
- ¿Se puede transformar toda solución recursiva en una solución iterativa?
- ¿Por qué el introsort se convierte de quicksort a heapsort después de cierta profundidad?
- En el algoritmo de búsqueda A * deberíamos tener una lista abierta y otra cerrada. ¿Cómo los implementa utilizando tanto el hashmap como una cola prioritaria en Java?
