如何证明堆数据结构中的子节点位置为2 * n和2 * n + 1？

Question

这不是一道作业题，我今天学习了堆数据结构，但我不知道如何证明该关系式的正确性。谢谢。

- user2648841

---

那不是一个结果，它更或多或少是堆的定义。 - H H

Answer 1

归纳证明：

1. 根节点的子节点 (1) -> 子节点1= 2*1=2 , 子节点2= 2*1 + 1 = 3 正确
2. 假设第k个元素的子节点为 -> 子节点1= 2k , 子节点2=2k+1
3. 证明第(k+1)个元素的子节点是子节点1= 2*(k+1), 子节点2=2(k+1) + 1 (证明如下)

证明3: 由于假设第k个元素的子节点分别为2k和2k+1（基于假设），那么，其后两个元素分别为2k+2和2k+3.

2k+2 = 2(k+1) (第一个子节点 k+1 的正确性已经被证明)(a)

2k+3 = 2k + 2 + 1 = 2(k+1) + 1 (第二个子节点 k+1 的正确性已经被证明)(b)

从(a) & (b) --> 可以得出3成立，因此元素n的子节点为2n和2n+1。

- nafas

---

当然，归纳证明很简单易懂，但它并不能让你记住事情，因为它是基于猜测的（先猜测再证明）。例如，你可以轻松地通过归纳证明1+..+n = n * (n + 1) / 2，但我永远不会用这种方式教孩子这个公式。它不会给你任何直觉，完全没有感情色彩。如果没有选择，我只会坚持使用归纳法。 - Egor Okhterov

我理解归纳法，而且我并没有说归纳法是通过猜测证明的 =) - Egor Okhterov

@Pixar 看看这个：https://math.stackexchange.com/questions/2260/proof-for-formula-for-sum-of-sequence-123-ldotsn 。虽然它是正确的，但并不是一个完整和严谨的证明。它只是说你可以把数字加起来。 - nafas

那个帖子里有29个回答。你所指的是哪个答案？ - Egor Okhterov

如果我要教别人这个公式，我宁愿向他展示被接受的答案，而不是通过归纳证明来教他 =) - Egor Okhterov

Answer 2

以下是我认为更直观且有洞见的无需归纳证明。以下是证明该关系的4个心理步骤。

将树展平。

让我们按以下方式枚举树的所有顶点：
这些顶点在数组中的样子如下：

在数组中隔离兄弟节点。

我们可以注意到，每两个连续的节点（除第一个节点外）都是某个公共顶点的子节点：
1 [ 2 3 ] [ 4 5 ] [ 6 7 ] [ 8 9 ]

以不同的方式构建此数组。

现在让我们逆向思考。如果我们有一对数组：[(2, 3), (4 5), (6, 7), (8, 9)]，并且我们想将它们聚合到单个数组中，怎么办？

假设我们已经放置了前3对：
[ 2 3 ] [ 4 5 ] [ 6 7 ] 数字8在最终数组中的索引是多少？ 我们知道，我们已经放置了3对，并且它们在开头占据了3 * 2 = 6个位置，因此我们将占据第7个位置。

如果我们编写成对放置的代码，它将如下所示：

pair<int, int> pairs[4] = { {2, 3}, {4, 5}, {6, 7}, {8, 9} };
int aggregate[2 * 4];
for (int i = 0; i < 4; i++)
{
    aggregate[2 * i] = pairs[i].first;
    aggregate[2 * i + 1] = pairs[i].second;
}

关键部分是数组 聚合[2 * i] 的索引。在这段代码中，显然可以看到为什么要乘以2 - 我们这样做是因为我们必须跳过前面的i-1对。

树的展开和成对聚合的结合

现在我们需要看到建立成对聚合数组和二叉树展平之间的对应关系。每对兄弟都有一个父母。如果两个兄弟(2, 3)和(4, 5)在数组中相邻，则它们的父母也相邻。兄弟姐妹(2, 3)的父亲是1，兄弟姐妹(4, 5)的父亲是2，兄弟姐妹(6, 7)的父亲是3。所以，在这个成对的数组中，父亲就像是索引pairs[4] = {(2, 3), (4, 5), (6, 7), (8, 9)}，当我们使用2 * i来访问其左侧子节点时，我们可以认为是跳过由前面顶点生成的-1对孩子。

- Egor Okhterov