Question

Please answer full question thoroughly (A- D) showing detailed work. SUBMIT ORIGINAL work and ensure it is correct for thumbs up.

a) Show that an n-element heap has height  

b) Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.

c) Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

d) Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by  

Answer 1

a).

In this n element is an heap and heap is a tree and heap is satisfy there all the properties are:In their all the child nodes are less and greter than its parent node for a min type heap.

The leaves of a heap fill the h or h-1 node.

Height of heap = O(n).

b).

Assume that the root of sub tree is same position a[i].

The max heap property = A[i] >=A[j=2i].

In case if node i is left child and A[i] >= A[k = 2*i+1], if node i its right sub tree.

But A[j] >=A[2j] if in case j node is left child and A[k] >= A[2k+1].

In case k node is left child and A[K] >= A[2*K+1] if k node is a right sub tree and this steps are followed continous.

Hence A[i], in this the root of the sub tree is greater than the value of any child in the sub tree .so that it contains larger value in the subtree.

c).

The max heap property that is node's value is greater than the child nodes value and the maximum element it will be become the root node.