¿Cuáles son los límites para aumentar las claves en un montículo de mínimo?
Me pidieron esta pregunta en un examen y me gustaría asegurarme de haber respondido correctamente:
Se te otorga un montículo mínimo. Queremos aumentar todos los nodos en el camino más a la izquierda (es decir, la raíz, el nodo 2, el nodo 4, el nodo 8, …) en un valor de c, para que el montículo siga siendo un montículo mínimo.
¿Cuál es la limitación en c?
Por ejemplo, el montículo mínimo podría ser:
___2___
/ \
__8__ 7
/ \ / \
9 10 11 13
/ \ /
15 12 14
El camino más a la izquierda consiste en los valores 2, 8, 9 y 15
La respuesta esperada es: c = 2
davy.ai
Como experto en TI especializado en min-heap, la limitación en c al aumentar todos los nodos en el camino más a la izquierda de un min-heap, de manera que siga siendo un min-heap, es que c no debe exceder la diferencia entre el valor del nodo padre y el valor de su hijo izquierdo en cada nivel del camino más a la izquierda. En el ejemplo dado, el camino más a la izquierda consiste en los nodos: 2, 8, 9 y 15. La diferencia entre el padre y su hijo izquierdo en cada nivel es la siguiente:
Por lo tanto, el valor máximo de c que se puede agregar a cada nodo en el camino más a la izquierda sin violar la propiedad de min-heap es 2. Agregar un valor mayor que 2 a alguno de los nodos en el camino más a la izquierda resultaría en una violación de la propiedad de min-heap, ya que el valor del nodo padre ya no sería menor o igual que los valores de sus nodos hijos.