Gilt die HEAP-Eigenschaft in der Definition von Binärhaufen rekursiv?

Question

Die Definition von binary heaps sagt, dass es sich um einen vollständigen Binärbaum handeln sollte, und es sollte der HEAP-Eigenschaft folgen, wobei der in jedem Knoten in jedem Knoten gespeicherte Taste entweder größer oder gleich oder kleiner istSchlüssel in den Kindern des Knotens.

Im obigen Baum ist der Knoten mit dem Wert 70 größer als sein Elternteil 10, der die Haufeneigenschaft bricht.70 ist jedoch auch größer als 40 und liegt jedoch im Teiltree von 40. Werden wir sagen, dass die Haufeneigenschaft auch bei 40 bricht, obwohl 40 größer als seine beiden Kinder 10 und 2?

In einfachen Begriffen sollte jeder Knoten im Teiltree einer Wurzel kleiner als die Wurzel sein?

Answer 1

Ich würde denken, dass die meisten Menschen nur sagen würden, dass die Haufeneigenschaft nur für einen Vertex und seine unmittelbaren Kinder gilt, da es eine ausreichende Definition ist, um die "rekursive" Haufen-Eigenschaft überall aufrechtzuerhalten.Es ist eine sauberere Art, darüber nachzudenken (Sie müssen nur o (1) Objekte pro Scheitelung überprüfen, um zu überprüfen, ob ein Baum ein Haufen ist, im Gegensatz von O (n) pro Scheitelung).

Ich weiß nicht, ob es genau ein Konsens ist, und vielleicht denken einige andere Menschen anders.