algorithm - 找到堆的父级和子级的方程式背后的直觉是什么？

Question

查找堆的父子节点的算法是：

家长：i / 2

左孩子：2i

右孩子：2i + 1

我试过在纸上画出数组表示，但我不确定我是否完全直观地理解了它。

Answer 1

关键是元素以广度优先的方式枚举，并且索引是基于 1 的（它们从 1 开始而不是 0）。

    1
   / \
  2   3
 / \ / \
4  5 6  7

以3为例

2*3   = 6   left child
2*3+1 = 7  right child

至少在进行整数除法的语言中，将 6 和 7 除以 2 得到 3。

以这种方式继续编号，您的直觉应该会起作用。通常，乘以 2 将始终给出左孩子的索引。右孩子是左孩子的继任者（+1）。整数除以 2 的工作原理相同（它“丢弃”余数。）