首页 > 后端开发 > C++ > 正文

二叉堆的数组表示

PHPz
发布: 2023-09-04 22:45:05
转载
696 人浏览过

遵循堆排序属性的完全二叉树称为二叉堆

根据二叉堆的排序方式,它可以分为两种类型:

最小堆是节点的值大于或等于其父节点的值的堆。最小堆的根节点最小。

最大堆是节点的值小于或等于其父节点的值的堆。最大堆的根节点最大。

二叉堆的值通常表示为一个数组。二叉堆的数组表示如下:

  • 根元素的索引为0。

  • 如果i是数组中节点的索引,则与该节点相关的其他节点的索引如下:

    • 左孩子:(2*i)+1

    • 右孩子:(2*i)+2

    • 父节点:(i-1)/2

使用上述数组表示规则,我们可以将堆表示为数组:

二叉堆的数组表示

1 4 7 8 9 11 12

现在,我们可以讨论基于排序的堆的类型:

  • 最小堆 - 根节点具有最小值。节点的值大于父节点的值。

示例:

二叉堆的数组表示

数组表示:

1 4 7 6 9 10 8
  • 最大堆 - 根节点具有最大值。节点的值小于父节点的值。

示例:

二叉堆的数组表示

数组表示:

11 8 9 6 4 5 1

以上是二叉堆的数组表示的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板