Full and complete answers in order to get creditDetailed and

Full and complete answers in order to get credit.Detailed and elaborated answer, no one-liner answer would be accepted.Thank you.

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

(b) Determine, with reasoning, what are the minimum and maximum numbers of elements in a heap of height h.

Solution

a)

The smallest element would reside in one of the leaf nodes, since the max heap property specifies that A[Parent(i)] >= A[i] (or strictly > with distinct elements). If a node had any children, it could not be the smallest element. If not, it will have its own subtree and is larger than any element on that subtree, which contradicts the fact that it is the smallest element.

b)

The range of values depends on how the height of the heap is considered. Some authors consider leaf node to be height 0, whereas others consider leaf node to be at height 1. So throughout the web, you shall see plenty of conflicting ranges. For most parts, you can consider, height as the number of edges from that node to its deepest leaf.

Assuming leaf node is at height 0, the minimum number of elements in a heap is 2^h, and the maximum number of elements in the heap is 2^(h+1) - 1

Assuming leaf node is at height 1, the minimum number of elements in a heap is 2^(h-1), and the maximum number of elements in the heap is 2^h - 1