Question

Assume that a heap is implemented using an array called items where the root of the heap is stored in items[0]. Provide the mathematical proof of the following formulas that calculate the indices of the children and parent of any node items[i]. Left child of items[i] is items [2xi + 1] - Right child of items[i] is items [2xi + 2] Parent of items[i] is items[[(i-1)/2]]

Answer 1

In a heap using array, the node can be located via simple formula or arithmetic using the node's index. Below I will derive the equivalent equations for heaps with their root at index 0, also additional nodes on heaps with their root at index 1. I'll define the level of a node as its distance from the root, such that the root itself occupies level 0.

CHILD NODES :-

Let node 'i' be located at the level L, and keep in mind that any level contains exactly   nodes. There are   nodes contained in the layers since, the root is stored at 0 and kth node will be stored at index (k-1). These Observations concludes that following expression for the index of the last node in layer l.

Assume there be j nodes after node i in layer L, such that

Each of these j nodes must have exactly 2 children, so there must be two j nodes which separates i's right child from the end of its layer L+1.

Note that left child of any node is 1 place before its right child, we get .

If the root is located at index 1 instead of 0, the last node in each level is instead at index . Using this throughout yields and for heaps with their root at 1.

PARENT NODES:-

Every node is either the left or right child of its parent, Therefore:-

Hence,

consider the expression .

If node 'i' is a left child, this gives the result , Also, it also gives the correct result if node 'i' is a right child. In this case, should be even, and hence should be odd.

Therefore, its parent can be found using :

.