找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法系列: 10大常见排序算法: 堆排序(1)堆的数据结构

admin 2019-3-13 22:10 248人围观 C++相关


本课程是从少年编程网转载的课程,目标是向中学生详细介绍计算机比赛涉及的编程语言,数据结构和算法。编程学习最好使用计算机,请登陆 www.3dian14.org (免费注册,免费学习)。



一句
 堆就是用数组实现的二叉树,特省空间



把二叉树存放在数组里

这是一个二叉树,想一下如何把这个二叉树存在数组里?

当然,父节点和子节点的关系也需要保存下来。换句话说,存储在数组中的数据可以再还原出原来的二叉树。



很简单,从最上面一层开始,按顺序放到数组里:



这个二叉树从最顶端的第0层开始,一共有4层。我们来看一下每一层有多少个节点,然后找到每一层第一个节点在数组里的下标值。



第0层的节点数: 2^0 = 1

第1层的节点数: 2^1 = 2

第2层的节点数: 2^2 = 4

第3层的节点数: 2^3 = 8

嗯,都是2的次方数

那么每一层的第一个节点在数组里的位置是前面所有节点数+1, 因为数组的索引是从0开始的,那么在数组中的索引位置需要减1:

第0层的第一个节点索引位置: 0

第1层的第一个节点索引位置: 2^0 + 1 - 1 = 2^0 = 2^1-1

第2层的第一个节点索引位置: 2^0+2^1 +1-1= 2^0+2^1= 2^2-1

第3层的第一个节点索引位置:  2^0+2^1 + 2^2 + 1-1= 2^0+2^1 + 2^2 = 2^3-1

规律是: 第n层的第一个节点是索引位置 = 2^n -1     (n = 0,1,2...)



问题:




答案:

因为第n层的第一个节点是2^n -1, 所以x在第n层。


下面来推导计算第几层的简单公式:





堆中父节点和子节点的索引变换

如果 i 是节点的索引, 下面我们来找到它的父节点和子节点在数组中的位置

left(i)  表示二叉树中i的左子节点索引位置

right(i)  表示二叉树中i的右子节点索引位置

parent(i) 表示二叉树中i的父节点索引位置

我们来看一下节点i的同一层第一个节点的子节点。这里i是5,同层第一个节点是3.




节点3的左子节点是7, 也是下一层的第一个节点。 现在来使用每层第一个节点的计算公式: 2^n - 1   




也就是左子节点 = 【该节点索引值】 乘以【2】 加  【1】


现在从本层的第一个节点3移动到节点j (5). 我们注意到:当我们在同一层中向右移动节点时(3到5),因为每个节点有左右2个子节点,相应的子节点索引值以2倍的距离移动(7到11)。



上图显示子节点层的移动距离是父节点层的2倍









也就是对于一个节点(5),对于它的左子节点的索引值依然是 2倍的值加1.


:总结一下:

一句
这是堆中父节点和子节点索引的换算公式



请点击阅读原文来观看动画交互课件


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:中学生编程与信息学竞赛自学,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......