A propriedade Heap na definição de montes binários se aplica recursivamente?

Question

A definição de binary heaps diz que deve ser uma árvore binária completa e deve seguir a propriedade heap onde de acordo com a propriedade Heap, a chave armazenada em cada nó é maior ou igual ou menor ou igual ou menor ou igual aochaves nos filhos do nó.

Na árvore acima, o nó com valor 70 é maior que o pai 10 quebrando a propriedade Heap.No entanto, 70 também é maior que 40 e está na subárvore de 40. Dizeríamos que a propriedade Heap também está quebrando 40, mesmo que 40 seja maior do que seus dois filhos 10 e 2?

em termos simples, todos os nó da subárvore de uma raiz são menores que a raiz?

Answer 1

Eu acho que a maioria das pessoas simplesmente diria que a propriedade de heap se aplica apenas a um vértice e suas crianças imediatas, porque é uma definição suficiente para manter a propriedade "recursiva" em todos os lugares.É uma maneira mais limpa de pensar sobre isso (você só precisa verificar o (1) objetos por vértice para verificar se uma árvore é um monte, em oposição a O (n) por vértice).

Eu não sei se existe exatamente um consenso sobre isso, e talvez algumas outras pessoas pensem de forma diferente.