formula for index of a children of a node in a d-ary heap

Question

Assume we have a d-ary heap and we index the nodes from top to bottom and from left to right(starting with 1). Then the children from node i are the nodes with index di,...,di+(d-1). I read this formula in a couple of books but in none of them were an explanation why these formulas are true. Maybe I am overlooking something but is it really that clear that these formulas are true?

Answer 1

I find d * i + 2 - d for the index of the first child, if items are numbered starting from 1. Here is the reasoning

Each row contains the children of the previous row. If n[r] are the number of items on row r, one must have n[r+1] = d * n[r], which proves that n[r] = d**r if the first row is numbered 0. The index of the first item of row r is f[r] = 1 + (d**r - 1)/(d - 1) by the sum of geometric sequences. If item X with number i is on row r, let's write i = f[r] + k with 0 <= k < d**r. There are k items on the row before X, hence there are d * k items before X's first child on row r+1. The index of X's first child is f[r+1] + d * k = f[r+1] + d * (i - f[r]) The calculus gives d * i + 2 - d for the index of the first child.

Actually, if we start numbering the items from 0 instead of 1, the formula becomes simply d * i + 1 for the index of the first child, and this can be easily proven by induction because the index of the first child of item i+1 is obtained by adding d, but (d * i + 1) + d = d * (i + 1) + 1.

Answer 2

Maybe this diagram will help, at least for d=2:

 1
 2                       3
 4           5           6           7
 8     9    10    11    12    13    14    15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31