Hi guys, I'm wondering why the leafs of binary complete tree is always satisfying the property of min/max heap , and we are saying that immediately if we arrive a leaf then it satisfies the property of min/max heap, why?! may anyone please explain and elaborate the reason ..
thanks in advance to the helpers
Post a complete program that demonstrates the problem.
You might want to start by answering these questions for yourself:Originally Posted by RyanC
- What is a "binary complete tree"?
- What is a "min/max heap"?
- What is this property that you refer to?
Look up a C++ Reference and learn How To Ask Questions The Smart Way
1. It's binary tree that's in every level all the positions are filled with nodes.
2. Min heap is : the valur of the root is greater than it's children.
3. I don't know why its trivial thats the leafs are satisfying minmum heap property. Meaning they are trivially min heap
The definition of min heap is: if there's children, then the children of a root is smaller than the root(its parent) , so how we get the conclusion that when there's no children(root is a leaf) then its in trivially min heap?!
In math if A->B then if A doesn't occur, all possibilities are accepted ! so here there's a root which doesn't have children, then we can say that root is min heap also there's a possibility to say it's not a min heap because the condition A doesn't occur, then all possibilities are accepted
That does not describe a complete binary tree.
That incompletely describes a max heap. I was hoping that you would list in detail both the properties of a min (or max) heap, and then in your next answer explain which one you were talking about and why.
I asked "what is this property that you refer to?", not what are you confused about.
I think you expressed this really poorly in posts #1 and #4. Instead of talking about "the leafs of binary complete tree is always satisfying the property of min/max heap" or even that "its trivial thats the leafs are satisfying minmum heap property", you should have asked: "why does a complete binary tree in which the root is a leaf trivially satisfy the other property of a min (or max) heap, i.e., that the value of each node is no greater than (or no less than) the values of its children"?
Actually, the more common way of expressing that min heap property is to say "the value of each node is no greater than (or equivalently, less than or equal to) the values of its children". So, if there are no children, then this is vacuously true, i.e., it is an example of how all the members of an empty set satisfy any property that can be ascribed to them: if there are no children, then it is vacuously true that the value of each node is greater than the values of its children.
This means that a complete binary tree in which the root is a leaf is a min heap, it is also a max heap, it is also a binary search tree, and it is a balanced binary tree. Hence, whichever one we chose it to be depends on whichever one suits our purposes.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
I got you but by definition of heap is : if there's children then the root is bigger/smaller that its children respectively to max/min heap.
So now can we conclude that if there's no children then the claim(min/max heap) is trivial satisfying?!
That's a wrong definition. You're only talking about the root, whereas the heap property talks about every node.
Anyway, you already reasoned that out earlier. Yes, because given A->B, if A is false then any B could be true. That's the same underlying idea as the notion of vacuous truth. But it isn't good for your example to use "if there are children", because then instead of using vacuous truth, we could just add the clause "otherwise the heap property is satisfied".
Look up a C++ Reference and learn How To Ask Questions The Smart Way
