二进制堆可以用数组来表示,数组是一种线性数据结构,而树是一种非线性数据结构。这是否意味着用数组表示的二进制堆不再是树?
ipakzgxi1#
您混淆了 * 模型 *(堆的概念视图)和 * 实现 *。二叉堆是一个在数组中实现的树。也就是说,我们分配一个固定的内存块,并像引用树一样引用它。我们可以这样做是因为二叉堆是一种非常特殊的树类型。在概念上,这与我们实现二维数组的方式没有太大的不同。考虑一个声明为a[3,4]的二维数组。大多数语言将其分配为单个内存块--一个线性数组--大小为12。但是我们将其作为一个二维结构来寻址。编译器将我们的二维寻址转换为一维数组索引(假设以行为主排序),如下所示:在我们的二维视图中,它看起来像这样:因此a[2,3]解析为索引7。因为一个二叉树堆是一个完整的二叉树,其中除了最后一层之外的所有层都是满的,而最后一层是左填充的(即所有的空白空间都在最后一层的右边),我们可以用覆盖二维数组的方法在数组上覆盖一个树结构。我们知道数组的第一个元素是堆的根,接下来的两个元素是根的子元素,接下来的四个元素是这些子元素的子元素,以此类推,所以在一个有7个节点的二进制堆中,我们有:
a[3,4]
a[2,3]
这将导致数组的视图如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
或者,以树的形式查看:
二叉堆仍然是一棵树,我们只是利用我们对二叉堆的特殊性质的了解,来实现它,比实现其他类型的树更有效。是的,我们使用线性数据结构来实现非线性数据结构,但我们使用的所有数据结构都是如此。(想想8086和之前的版本)将内存视为一个大数组,软件将其分为不同的区域,用于操作系统、程序代码、处理器堆栈、进程堆等,而在进程堆内部(同样是一个大的线性数据结构),程序会分配和释放单个块来构建非线性数据结构,即使是今天的系统,通过内存虚拟化和地址转换,事情的工作方式也大致相同:你的程序分配大块的线性内存并管理它们,为非线性数据结构划分出小块。接下来是链表:一个线性的数据结构,它是用一个非线性的数据结构来实现的。同样,模型是一个列表--一个线性的数据结构。实现根本不是线性的。然后考虑在数组中实现链表。数组的每个元素包含节点数据和列表中下一项的索引。按顺序遍历,列表节点可能位于数组索引1,7,5,4,6,2,3.数据结构是线性的还是非线性的,取决于你如何看待问题,或者你所关注的是实现的哪一部分。同样,列表的模型是线性的,它的实现是在一个线性数据结构(数组)中,但是列表中的第一个节点在数组的开头,第二个节点在数组的末尾,中间的节点基本上是随机排列的,根本不是线性的!您必须学会将模型与实现分离。
h79rfbju2#
答案是否定的,我们可以用我们想要的方式来表示,但它将是一棵树。问题是在这里,当我们把它表示为数组时,对二进制堆的所有属性是否都没有限制。
2条答案
按热度按时间ipakzgxi1#
您混淆了 * 模型 *(堆的概念视图)和 * 实现 *。
二叉堆是一个在数组中实现的树。也就是说,我们分配一个固定的内存块,并像引用树一样引用它。我们可以这样做是因为二叉堆是一种非常特殊的树类型。在概念上,这与我们实现二维数组的方式没有太大的不同。
考虑一个声明为
a[3,4]
的二维数组。大多数语言将其分配为单个内存块--一个线性数组--大小为12。但是我们将其作为一个二维结构来寻址。编译器将我们的二维寻址转换为一维数组索引(假设以行为主排序),如下所示:在我们的二维视图中,它看起来像这样:
因此
a[2,3]
解析为索引7。因为一个二叉树堆是一个完整的二叉树,其中除了最后一层之外的所有层都是满的,而最后一层是左填充的(即所有的空白空间都在最后一层的右边),我们可以用覆盖二维数组的方法在数组上覆盖一个树结构。
我们知道数组的第一个元素是堆的根,接下来的两个元素是根的子元素,接下来的四个元素是这些子元素的子元素,以此类推,所以在一个有7个节点的二进制堆中,我们有:
这将导致数组的视图如下所示:
或者,以树的形式查看:
二叉堆仍然是一棵树,我们只是利用我们对二叉堆的特殊性质的了解,来实现它,比实现其他类型的树更有效。
是的,我们使用线性数据结构来实现非线性数据结构,但我们使用的所有数据结构都是如此。(想想8086和之前的版本)将内存视为一个大数组,软件将其分为不同的区域,用于操作系统、程序代码、处理器堆栈、进程堆等,而在进程堆内部(同样是一个大的线性数据结构),程序会分配和释放单个块来构建非线性数据结构,即使是今天的系统,通过内存虚拟化和地址转换,事情的工作方式也大致相同:你的程序分配大块的线性内存并管理它们,为非线性数据结构划分出小块。
接下来是链表:一个线性的数据结构,它是用一个非线性的数据结构来实现的。同样,模型是一个列表--一个线性的数据结构。实现根本不是线性的。
然后考虑在数组中实现链表。数组的每个元素包含节点数据和列表中下一项的索引。按顺序遍历,列表节点可能位于数组索引1,7,5,4,6,2,3.数据结构是线性的还是非线性的,取决于你如何看待问题,或者你所关注的是实现的哪一部分。同样,列表的模型是线性的,它的实现是在一个线性数据结构(数组)中,但是列表中的第一个节点在数组的开头,第二个节点在数组的末尾,中间的节点基本上是随机排列的,根本不是线性的!
您必须学会将模型与实现分离。
h79rfbju2#
答案是否定的,我们可以用我们想要的方式来表示,但它将是一棵树。问题是在这里,当我们把它表示为数组时,对二进制堆的所有属性是否都没有限制。