Question

Data Structures and Algorithm Analysis in Java by Weiss: Exercise 6.8

Show the following regarding the maximum item in the heap:

A) It must be at least one of the leaves.

B) There are exactly [N/2] leaves.

C) Every leaf must be examined to find it.

Answer 1

As per the heap order property ,min heap the value of each node is greater than or equal to value of its oarentwith minim value at the root.with this ,it can be proven that max element in heap should be at its leaf

B)

A complete tree of depth k has exactly (2^k+1) -1 nodes.

Now assume at depth k,up to level k-1 ,the tree is complete and has( 2^k) -1 nodes.

Each leaf on kth level will have a parent and parent will be at n-(2^k+1)+1/2 .I.e

Thus out of (2^k-1) nodes at k-1 level,[n-2^k+1/2]. Are aprenrs and the rest 2^(k-1) -[n-2^k+1/2] are leaves.

So the total no of leaves is n-2^k+1+2(k-1)- [n-2^k+1/2] which will be equal to N/2 leaves

Example:take a perfect tree of depth 2,it will have total of (2^k+1)-1=7nodes =N

Now calculate the leave nodes using above formula 7-2+1+2^0-[7-2^1+1/2] []-upper bound of value.=7-3=4 nodes which is upper bound of 7/2 i.e N/2

C)

If we want to add anode which is greater than the max element of the heap ,then the value which we want to insert will definitely end up at one of the leaves of heap or if we may need to insert any other number also we have to traveser the entire heap and then we can insert the element .thus every leaf must be examined to find out the max item.