La propriété de tas dans la définition des tas binaires s'applique-t-elle de manière récursive?

Question

La définition de binary heaps dit qu'il devrait s'agir d'un arbre binaire complet et devrait suivre la propriété HEAP où selon la propriété HEAP, la clé stockée dans chaque nœud est supérieure ou égale à ou égale à laclés dans les enfants du nœud.

Dans l'arbre ci-dessus, le nœud avec valeur 70 est supérieur à son parent 10 brisant la propriété de tas.Cependant, 70 est également supérieur à 40 et réside dans le sous-arbre de 40. Dirons-nous que la propriété du tas se brise également à 40 ans, même si 40 est supérieure à ses deux enfants 10 et 2?

en termes simples si chaque nœud de la sous-arbre d'une racine est inférieur à la racine?

Answer 1

Je penserais que la plupart des gens diraient simplement que la propriété du tas ne s'applique qu'à un sommet et à ses enfants immédiats, car il s'agit d'une définition suffisante pour maintenir la propriété "récursive" du tas partout.C'est une façon plus propre d'y penser (vous n'avez besoin que de vérifier O (1) d'objets par sommet pour vérifier qu'un arbre est un tas, par opposition à O (n) par sommet).

Je ne sais pas s'il y a exactement un consensus à ce sujet, et peut-être que d'autres personnes pensent différemment.