java - 为什么二叉堆是树结构？

Question

二叉堆可以使用数组来表示，数组是一种线性数据结构，与树不同，树是一种非线性数据结构。这是否意味着使用数组表示的二叉堆不再是树？

Answer 1

您混淆了模型(堆的概念 View )与实现。

二叉堆是在数组中实现的树。也就是说，我们分配一个固定的内存块并像树一样引用它。我们可以这样做，因为二叉堆是一种非常特殊的树类型。从概念上讲，这与我们实现二维数组的方式没有太大不同。

考虑一个声明为 a[3,4] 的二维数组。大多数语言将其分配为大小为 12 的单个内存块(线性数组)。但我们将其视为二维结构。编译器将我们的 2D 寻址转换为一维数组索引(假设行优先排序)，如下所示:

 1 2 3 4 5 6 7 8 9 10 11 12
| Row 1 | Row 2 |  Row 3

在我们的二维 View 中，它看起来像这样:

 1  2  3  4
 5  6  7  8
 9 10 11 12

因此 a[2,3] 解析为索引 7。

这与堆有什么关系？

因为二叉堆是一个完全二叉树，其中除了最后一层之外的所有级别都已满，并且最后一层是左填充的(即所有空白空间都在最后一层的右侧)，因此我们可以覆盖在数组上构建树结构的方式与我们覆盖二维数组的方式大致相同。

我们知道数组的第一个元素是堆的根。我们知道接下来的两个数组元素是根的子元素。接下来的四个元素是那些 child 的 child ，依此类推。因此，在具有 15 个节点的二叉堆中，我们有:

• 索引 1 - 根节点
• 索引 2 和 3 - 根节点的子节点
• 索引 4、5、6、7 - 根的子级的子级 (4 和 5 是索引 2 处节点的子节点。6 和 7 是索引 3 处节点的子节点)。
• 索引 8 到 15 - 索引 4-7 处的节点的子节点。

这会导致数组 View 如下所示:

1
2 3
4 5 6 7
8 9 10 11 12 13 14 15

或者，将其视为一棵树:

            1
      2           3
   4     5     6     7
  8 9  10 11 12 13 14 15

二叉堆仍然是一棵树。我们只是利用我们对二叉堆特殊性质的了解来比实现其他类型的树更有效地实现它。

是的，我们正在使用线性数据结构来实现非线性数据结构。但我们使用的所有数据结构都是如此。早期的处理器(例如 8086 及之前的处理器)将内存本质上视为一个大阵列。软件本质上会将其分为不同的区域，用于操作系统、程序代码、处理器堆栈、进程堆等。在进程堆(同样是一个大的线性数据结构)内，程序将分配和取消分配各个 block 来构建非线性数据结构。即使今天的系统具有内存虚拟化和地址转换，事情的工作方式也大致相同:您的程序分配大块线性内存并管理它们，为非线性数据结构分配小块。

然后是链表:用非线性数据结构实现的线性数据结构。同样，模型是一个列表——一种线性数据结构。 实现根本不是线性的。

然后考虑在数组中实现链表。数组的每个元素都包含节点数据和列表中下一项的索引。按顺序遍历，列表节点可能位于数组索引 1,7,5,4,6,2,3 处。这是线性还是非线性数据结构取决于您如何看待问题。或者也许您正在查看实现的哪一部分。同样，列表的模型是线性的。并且实现是在线性数据结构(数组)中。但列表中的第一个节点位于数组的开头，第二个节点位于数组的末尾，中间的节点基本上是随机顺序的。它根本不是线性的!

您必须学会将模型与实现分开。