首页 >后端开发 >C++ >二叉堆的数组表示

二叉堆的数组表示

PHPz
PHPz转载
2023-09-04 22:45:05704浏览

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

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

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

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

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

  • 根元素的索引为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删除