在Heap中父子节点的关系:

P为父节点下标为Pi
P的左孩子下标为Pl = 2 * Pi + 1
P的右孩子下标为Pl = 2 * Pi + 2

证明:

P节点是树的第n层的第m个节点,则通过计算1n-1层所有的节点数,再加上节点在第n层的索引,可以得到P的索引为:

Pi = 2^0 + 2^1 + ... + 2^(n-2) - 1 + m = 2^(n-1) + m - 2

其左孩子的索引同样可以计算(第n+1层,第2 * m个节点):

Pl = 2^0 + 2^1 + ... + 2^(n-1) - 1 + 2 * (m -1) + 1 = 2^n + 2 * m - 3 = 2 * Pi + 1

右孩子(第n+1层,第2 * (m - 1) + 1个节点):

Pl = 2^0 + 2^1 + ... + 2^(n-1) - 1 + 2 * m = 2^n + 2 * m - 2 = 2 * Pi + 2

等比数列忘完了…