algorithm - 寻找堆的父项和子项的等式背后的直觉是什么？

Question

查找堆的父项和子项的算法是:

父级:i/2

左 child :2i

右 child :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 总是会给出左 child 的索引。右 child 是左 child 的后继者(+1)。整数除以 2 的工作原理相同(它“丢弃”余数。)