Hola. ¿Cómo se puede construir un heap usando filtrado descendente? Gracias
Empezando por un caso sencillo. Supongamos que con el arreglo representamos un árbol completo de dos niveles (la raíz y sus hijos). ¿Aplicando filtrado descendente a qué nodo del árbol (celda del arreglo) se obtendría un árbol que también cumpla la propiedad de orden de los heap?
Ahh claro, a la raíz. Ahora entendí. Y eso debería hacer repetidas veces hasta que la nueva raíz no pueda bajar más en el árbol, correcto? Sería O(n) el peor caso?
En ese ejemplo de árbol de dos niveles sí, alcanza con aplicar el filtrado en la raíz.
Pero en general no. Por ejemplo si el dato de la raíz ya es menor que sus dos hijos el filtrado descendente no va a modificar nada y sin embargo podría no cumplirse la propiedad de orden si se tienen en cuenta los nodos más profundos. Por ejemplo [2 3 4 1].
Lo que podemos afirmar es que si cada uno de los dos subárboles ya cumple la propiedad de orden y se aplica el filtrado descendente en la raíz entonces va a quedar todo el árbol cumpliendo la propiedad de orden.
Esto ocurre en los árboles de dos niveles porque los subárboles están trivialmente bien ordenados porque son hojas.
Entonces en un árbol genérico a cada uno de los nodos que están en el penúltimo nivel, que es raíz de un subárbol que no necesariamente cumple la propiedad de orden, se les puede aplicar el filtrado y lograr que cada uno de esos subárboles pase a cumplir dicha propiedad.
Como consecuencia de esto, para cada nodo del antepenúltimo nivel se cumplirá que sus dos subárboles cumplen la propiedad y por lo tanto se les puede aplicar el filtrado.
Siguiendo este razonamiento se puede hacer que todo el árbol cumpla la propiedad de orden.
Pero en general no. Por ejemplo si el dato de la raíz ya es menor que sus dos hijos el filtrado descendente no va a modificar nada y sin embargo podría no cumplirse la propiedad de orden si se tienen en cuenta los nodos más profundos. Por ejemplo [2 3 4 1].
Lo que podemos afirmar es que si cada uno de los dos subárboles ya cumple la propiedad de orden y se aplica el filtrado descendente en la raíz entonces va a quedar todo el árbol cumpliendo la propiedad de orden.
Esto ocurre en los árboles de dos niveles porque los subárboles están trivialmente bien ordenados porque son hojas.
Entonces en un árbol genérico a cada uno de los nodos que están en el penúltimo nivel, que es raíz de un subárbol que no necesariamente cumple la propiedad de orden, se les puede aplicar el filtrado y lograr que cada uno de esos subárboles pase a cumplir dicha propiedad.
Como consecuencia de esto, para cada nodo del antepenúltimo nivel se cumplirá que sus dos subárboles cumplen la propiedad y por lo tanto se les puede aplicar el filtrado.
Siguiendo este razonamiento se puede hacer que todo el árbol cumpla la propiedad de orden.
Hola, construí un algoritmo con filtrado descendente pero no logro ver como podría ser O(n).
Existen dos algoritmos con filtrado descendente O(n) y O(nlogn) o uno solo que es O(n)?
Existen dos algoritmos con filtrado descendente O(n) y O(nlogn) o uno solo que es O(n)?
Hola.
El análisis que hiciste según el cual el algoritmo es
puede ser correcto. Pero también puede ocurrir que se pueda hacer un análisis más detallado con el cual se llegue a que también es 
(recordemos que estamos hablando de orden 
, no de 
).
El análisis que hiciste tal vez fue que se aplica veces el filtrado descendente, que es 
en peor caso. ¿Puede ser? Eso estaría bien.
Pero en el análisis más detallado se tiene en cuenta que ese orden para el filtrado descendente corresponde a los casos en que se aplica a nodos cercanos a la raíz. Si el nodo está en los niveles más profundos, entonces el filtrado descendente sería
. Como hay muchos más nodos en los niveles más profundos que cercanos a la raíz se puede llegar a demostrar que el algoritmo es .
¿Esto va bien encaminado para aclarar la duda?
El análisis que hiciste según el cual el algoritmo es
puede ser correcto. Pero también puede ocurrir que se pueda hacer un análisis más detallado con el cual se llegue a que también es (recordemos que estamos hablando de orden , no de ).El análisis que hiciste tal vez fue que se aplica
veces el filtrado descendente, que es en peor caso. ¿Puede ser? Eso estaría bien.Pero en el análisis más detallado se tiene en cuenta que ese orden para el filtrado descendente corresponde a los casos en que se aplica a nodos cercanos a la raíz. Si el nodo está en los niveles más profundos, entonces el filtrado descendente sería
. Como hay muchos más nodos en los niveles más profundos que cercanos a la raíz se puede llegar a demostrar que el algoritmo es . ¿Esto va bien encaminado para aclarar la duda?