¿El montón de la propiedad en la definición de montones binarios se aplica recursivamente?
-
29-09-2020 - |
Pregunta
La definición de binary heaps
dice que debe ser un árbol binario completo y debe seguir la propiedad del montón donde de acuerdo con la propiedad del montón, la clave almacenada en cada nodo es mayor o igual o menor o menor o igual a laLlaves en los hijos de los nodos.
En el árbol anterior, el nodo con valor 70 es mayor que su padre 10 que rompe la propiedad del montón.Sin embargo, el 70 también es mayor que 40 y las mentiras en el subárbol de 40. ¿Decíamos que la propiedad del montón también se está rompiendo a los 40, aunque 40 es mayor que sus dos hijos 10 y 2?
En términos simples, ¿cada nodo en el subárbol de una raíz sea más pequeño que la raíz?
Solución
Pensaría que la mayoría de las personas solo dirían que la propiedad del montón se aplica solo a un vértice y sus hijos inmediatos, porque es una definición suficiente para mantener la propiedad "recursiva" del montón en todas partes.Es una forma más limpia de pensar en ello (solo necesita verificar objetos O (1) por vértice para verificar que un árbol sea un montón, a diferencia de O (N) por vértice).
No sé si existe exactamente un consenso sobre esto, y quizás otras personas piensen de manera diferente.