0
$\begingroup$

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children.

Binary tree

In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

In simple terms should every node in the subtree of a root be smaller than the root?

Improve this question
$\endgroup$
2
  • $\begingroup$ hm... I would say it does not apply recursively. Do you see any benefits to using the definition which is recursive? $\endgroup$
    – Kevin Wang
    Jun 9, 2020 at 0:24
  • $\begingroup$ @KevinWang I didn't think it in terms of benefits but rather the clarity of definition. $\endgroup$
    – Navjot Singh
    Jun 9, 2020 at 7:00

1 Answer 1

Reset to default
2
$\begingroup$

I would think that most people would just say that the heap property applies only to a vertex and its immediate children, because it's a sufficient definition to maintain the "recursive" heap property everywhere. It's a cleaner way to think about it (you only need to check O(1) objects per vertex to verify that a tree is a heap, as opposed to O(n) per vertex).

I don't know if there is exactly a consensus on this, and perhaps some other people think differently.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.