当前位置:   article > 正文

数据结构之【堆详解】_数据结构堆

数据结构堆

目录

树概念及结构

树的表示

二叉树概念及结构

二叉树的性质

堆的概念及结构

堆向下调整算法

普通情况建堆


树概念及结构

1.1 树的概念
树是一种 非线性 的数据结构,它是由 n n>=0 )个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的
有一个特殊的结点,称为根结点,根节点没有前驱结点 。除根节点外,其余结点被分成M(M>0) 个互不相交的集合 T1 T2 …… Tm ,其中每一个集合 Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有 0 个或多个后继。
因此,树是递归定义的
树的示意图:

节点的度: 一个节点含有的子树的个数称为该节点的度; 如上图: A 的为 6
叶节点或终端节点: 度为 0 的节点称为叶节点; 如上图: B C H I... 等节点为叶节点
非终端节点或分支节点: 度不为 0 的节点; 如上图: D E F G... 等节点为分支节点
双亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图: A B 的父节点
孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点; 如上图: B A 的孩子节点
兄弟节点: 具有相同父节点的节点互称为兄弟节点; 如上图: B C 是兄弟节点
树的度: 一棵树中,最大的节点的度称为树的度; 如上图:树的度为 6
节点的层次: 从根开始定义起,根为第 1 层,根的子节点为第 2 层,以此类推;
树的高度或深度: 树中节点的最大层次; 如上图:树的高度为 4(第一层从1开始)
【有的书上认为是3,第一层从0开始编号】
堂兄弟节点: 双亲在同一层的节点互为堂兄弟;如上图: H I 互为兄弟节点
节点的祖先: 从根到该节点所经分支上的所有节点;如上图: A 是所有节点的祖先
子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是 A 的子孙
森林: m m>0 )棵互不相交的树的集合称为森林,并查集其实就是一个森林
注意:

每一棵树,都是有根节点+多个字树构成,子树也是一样的构成

树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表 示法,孩子表示法、孩子兄弟表示法等等。
我们这里就简单的了解其中最常用的孩子兄弟表示法
图示:

上述表示法,左孩子右兄弟表示法
(从左往右数第一个孩子)
无论树中一个节点有多少个孩子,都可以表示,因为我只指向第一个孩子,剩下的孩子,让孩子之间用兄弟指针串起来
双亲表示法:
图示

 B和C是A的孩子,他俩存储的是双亲A的下标也就是0,D E F的双亲是B,他们三个存储的是双亲B的下标也就是1,剩下的依次类推。(不实用)
树在实际中的运用
(表示文件系统的目录树结构)

二叉树概念及结构

1 概念
一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树 的二叉树组成。
二叉树的特点:
1. 每个结点最多有两棵子树,即二叉树不存在度大于 2 的结点。
2. 二叉树的子树有左右之分,其子树的次序不能颠倒。

数据结构中的二叉树: 

特殊的二叉树:
1. 满二叉树: 一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K ,且结点总数是 (2^k) -1 ,则它就是满二叉树。
图示:

2. 完全二叉树 :完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K 的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 n 的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
图示:

但如果是这样那他就不是完全二叉树

意思就是除了最后一层,之前的必须是是满二叉树,最后一层可以不是满的但是最后一层从左到右必须是连续的,  

二叉树的性质

1. 若规定根节点的层数为 1 ,则一棵非空二叉树的 i 层上最多有 2^(i-1) 个结点 .
2. 若规定根节点的层数为 1 ,则 深度为 h 的二叉树的最大结点数是 2^h- 1 .
推导过程如图:

3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为 n0, 度为 2 的分支结点个数为 n2, 则有 n0 n2 1
4.完全二叉树中度为1的节点最多只有一个
5. 若规定根节点的层数为 1 ,具有 n 个结点的满二叉树的深度 h=Log2(n+1) . (ps Log2(n+1) log 2 为 底,n+1 为对数 )
【2^h-1=n,所以 h=Log2(n+1)

接下来用该性质练练手

1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为(
A 不存在这样的二叉树
B 200
C 198
D 199
答:根据上述性质 n0=n2+1;
        n0=199+1=200;
2. 在具有 2 n 个结点的完全二叉树中,叶子结点个数为(
A n
B n + 1
C n - 1
D n / 2
答:设度为0的结点为n0,度为1的为n1,度为2的为n2
n0+n1+n2=2n
n0+n1+n0-1=2n;(n0=n2+1)
2n0-1+n1=2n;(完全二叉树中度为1的节点最多只有一个,所以n1=1)
2n0=2n;
n0=
选A;
3. 一棵完全二叉树的节点数位为 531 个,那么这棵树的高度为(
A 11
B 10
C 8
D 12
答:设高度为h
2^h-1-x=531;(x为最后一层缺的结点的个数)
x的范围[0,2^(h-1)-1];(完全二叉树)
所以将答案往上述两个公示套,发现符合求的是B
如图:这一部分即为x

4. 一个具有 767 个节点的完全二叉树,其叶子节点个数为()
A 383
B 384
C 385
D 386
 答:
 n2+n1+n0=767;
 n0-1+n1+n0=767;
 2n0+n1=768;(完全二叉树中度为1的节点最多只有一个,所以n1=0,如果n1=1,则n0为小数)
 n0=38 选B;

堆的概念及结构

如果有一个关键码的集合 K = {k0 k1 k2 kn-1} ,把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2 i+1 Ki<= K2 i+2 (Ki >= K2 i+1 Ki >= K2 i+2) i = 0 1 2… ,则称为 小堆( 或大堆)。
堆就是一个完全二叉树。
堆的存储
堆的存储实际就是一个数组,逻辑结构上是一个完全二叉树
如图:

 将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

小根堆就是父亲小于等于孩子

大根堆是父亲大于等于孩子

堆的公式(孩子与父亲的关系)
父亲的下标是parent
leftchild=parent*2+1;
rightchild=parent*2+2;
parent=(child-1)/2;
如图:

堆向下调整算法

   现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整
时间复杂度是O(logN),因为向下调整与树的高度有关,最多调整高度次(完全二叉树的高度就是logN),不能数循环,要看思想.
思路:
1. 选出左右孩子中小的那一个数
2.小的这个孩子与父亲比
  a.如果小的孩子比父亲小,则跟父亲交换位置,并且吧原来孩子的位置当成父亲继续往下调整,直到走到叶子节点
 b.如果小的孩子比父亲大,则不需要处理,调整完成,整个树已经是小堆

对这样一个数组{27,15,19,18,28,34,65,49,25,37};调整思路如图 

接下来通过思路实现代码:

  1. void AdjustDown(int* a, int n, int parent)
  2. {
  3. //找出左右孩子小的那个
  4. int child = parent * 2 + 1; //左孩子
  5. while (child < n)
  6. {
  7. //找出左右孩子小的那一个
  8. if (a[child + 1] < a[child])
  9. {
  10. //默认左孩子小,如果右孩子小就++,加到右孩子
  11. ++child;
  12. }
  13. if (a[child] < a[parent])
  14. {
  15. Swap(&a[parent], &a[child]);
  16. parent = child; //孩子成为父亲
  17. child = parent * 2 + 1;
  18. }
  19. else //b情况
  20. {
  21. break;
  22. }
  23. }
  24. }

 注意看这个代码对上述例子是不会有任何问题的,但是他还存在一个潜在的风险

如果将上面的例子改动一个数字 如图:将28改为16

 

 那么当他进行到第三步时

 a[child+1]就会发生越界的问题,所以要对a[child+1]进行限制让他小于n,改进后如下

  1. void AdjustDown(int* a, int n, int parent)
  2. {
  3. //找出左右孩子小的那个
  4. int child = parent * 2 + 1; //左孩子
  5. while (child < n)
  6. {
  7. //找出左右孩子小的那一个
  8. if (child + 1 < n && a[child + 1] < a[child])
  9. {
  10. //默认做孩子小,如果右孩子小就++,加到右孩子
  11. ++child;
  12. }
  13. if (a[child] < a[parent])
  14. {
  15. Swap(&a[parent], &a[child]);
  16. parent = child;
  17. child = parent * 2 + 1;
  18. }
  19. else //b情况
  20. {
  21. break;
  22. }
  23. }
  24. }

完整代码如下:

  1. #include <stdio.h>
  2. void Swap(int* p1, int* p2)
  3. {
  4. int tmp = *p1;
  5. *p1 = *p2;
  6. *p2 = tmp;
  7. }
  8. void AdjustDown(int* a, int n, int parent)
  9. {
  10. //找出左右孩子小的那个
  11. int child = parent * 2 + 1; //左孩子
  12. while (child < n)
  13. {
  14. //找出左右孩子小的那一个
  15. if (child + 1 < n && a[child + 1] < a[child])
  16. {
  17. //默认做孩子小,如果右孩子小就++,加到右孩子
  18. ++child;
  19. }
  20. if (a[child] < a[parent])
  21. {
  22. Swap(&a[parent], &a[child]);
  23. parent = child;
  24. child = parent * 2 + 1;
  25. }
  26. else //b情况
  27. {
  28. break;
  29. }
  30. }
  31. }
  32. int main()
  33. {
  34. //前提左右字树是小堆
  35. int a[] = { 27,15,19,18,28,34,65,49,25,37 };
  36. int n = sizeof(a) / sizeof(a[0]);
  37. AdjustDown(a, n, 0);
  38. return 0;
  39. }

运行后发现和我们预期的结果相同 

 

普通情况建堆

  特殊情况我们可以用向下调整算法,接下来由特殊转为一般,如果左右字树不是小堆,该如何将其调整为堆

eg: 对这样一个数组{15,18,28,34,65,19,49,25,37,27}进行调整

思路:从倒数的第一个非叶子节点(最后一个节点的父亲),从后往前,按照编号,依次作为子树去向下调整

以下就是建堆算法,根据parent=(child-1)/2;最后一个结点的父亲就是  [(n-1)-1  ]  /  2;n代表着数组中元素的个数。而除了最后一个结点的父亲之外,其余父亲结点的编号都是连续的直接减1即可,该建堆算法的时间复杂度是O(N);

  1. for (int i = (n - 1 - 1) / 2;i >= 0;i--)
  2. {
  3. AdjustDown(a, n, i);
  4. }

 完整代码:

  1. #include <stdio.h>
  2. void Swap(int* p1, int* p2)
  3. {
  4. int tmp = *p1;
  5. *p1 = *p2;
  6. *p2 = tmp;
  7. }
  8. void AdjustDown(int* a, int n, int parent)
  9. {
  10. //找出左右孩子小的那个
  11. int child = parent * 2 + 1; //左孩子
  12. while (child < n)
  13. {
  14. //找出左右孩子小的那一个
  15. if (child + 1 < n && a[child + 1] < a[child])
  16. {
  17. //默认做孩子小,如果右孩子小就++,加到右孩子
  18. ++child;
  19. }
  20. if (a[child] < a[parent])
  21. {
  22. Swap(&a[parent], &a[child]);
  23. parent = child;
  24. child = parent * 2 + 1;
  25. }
  26. else //b情况
  27. {
  28. break;
  29. }
  30. }
  31. }
  32. int main()
  33. {
  34. //前提左右字树是小堆
  35. int a[] = { 15,18,28,34,65,19,49,25,37,27 };
  36. int n = sizeof(a) / sizeof(a[0]);
  37. for (int i = (n - 1 - 1) / 2;i >= 0;i--)
  38. {
  39. AdjustDown(a, n, i);
  40. }
  41. return 0;
  42. }

 效果演示

 以上代码是构造小堆,构造大堆也很简单,只需要将小于改成大于即可,其余不做改变,如下

  1. if (child + 1 < n && a[child + 1] > a[child])
  2. {
  3. ++child;
  4. }
  5. if (a[child] > a[parent])
  6. {
  7. Swap(&a[parent], &a[child]);
  8. parent = child;
  9. child = parent * 2 + 1;
  10. }

以上例子构造大堆如下

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/622743
推荐阅读
相关标签
  

闽ICP备14008679号