バイナリヒープの定義のヒーププロパティは再帰的に適用されますか？

Question

binary heapsの定義は、それが完全なバイナリツリーであるべきであり、それはヒーププロパティに従って、各ノードに格納されているキーがそれ以上のものであるかそれ以下のキーであるべきです。ノードの子供の鍵

上記のツリーでは、値70のノードは、その親10よりも大きいため、ヒーププロパティを破ります。しかし、70は40を超え、40のサブツリーにあります.40は40であっても40歳以上であっても40歳以上の場合は40歳以下であると言っていますか？

単純な用語では、ルートのサブツリー内のすべてのノードがルートよりも小さい場合は？

Answer 1

ほとんどの人は、HEAPプロパティが頂点とその即時の子にのみ適用されると言っていると思います。これは、「再帰的な」ヒーププロパティをどこでも維持するのに十分な定義です。それについて考えるのはクリーンな方法です（あなたは頂点ごとのO（1）オブジェクトをチェックして、頂点あたりのO（n）ではなく、ツリーがヒープであることを確認するだけです）。

これについて正確な合意があるかどうかわからない、そしておそらく他の人が異なっていると思う。