La proprietà heap nella definizione di heap binari si applica in modo ricorsivo?

Question

La definizione di binary heaps dice che dovrebbe essere un albero binario completo e dovrebbe seguire la proprietà dell'heap dove in base alla proprietà heap, la chiave memorizzata in ciascun nodo è maggiore o uguale o inferiore o uguale atasti nei bambini del nodo.

Nell'albero sopra, il nodo con valore 70 è maggiore del suo genitore 10 che rompe la proprietà del mucchio.Tuttavia, 70 è anche maggiore di 40 anni e si trova nella sottostruttura di 40. Diremo che anche la proprietà dell'heap si sta rompendo a 40 anni, anche se 40 è maggiore dei suoi due figli 10 e 2?

In termini semplici dovrebbe ogni nodo nel sottosuolo di una radice essere più piccolo della radice?

Answer 1

Penserei che la maggior parte delle persone direbbe solo che la proprietà dell'heap si applica solo a un vertice e ai suoi figli immediati, perché è una definizione sufficiente per mantenere la proprietà heap "ricorsiva" ovunque.È un modo più pulito per pensarci (devi solo controllare o (1) oggetti per vertice per verificare che un albero sia un mucchio, al contrario di o (n) per vertice).

Non so se c'è esattamente un consenso su questo, e forse alcune altre persone pensano in modo diverso.