当前位置:   article > 正文

【数据结构】二叉树-堆

【数据结构】二叉树-堆

目录

一.树概念及性质

二.二叉树的概念与实现

三.堆的概念和结构

四.堆的实现

1.向下调整算法

2. 堆的创建

3.向上调整算法

 4.堆的删除

五.堆排序

六.堆-源码 


一.树概念及性质

树是一种非线性的数据结构,它是由数个节点组成的具有层次关系的集合。之所以叫做树,是因为长得就像一颗倒挂的树。就像下图一样,数据结构中的树是‘根’朝上,‘叶’朝下的。

 树的结构从一个特殊的节点出发:根节点,该节点没有任何的前驱节点,其余节点都是由此根节点延伸而来。

一棵树可以进行拆分为根节点和子树,如上图,第一个根节点下有三个子树,而每个子树又可以继续拆分为根节点和子树,直到某个根节点没有子树为止,从这个角度来看,树是递归定义的。

注意:树形结构中,子树之间不能有交集,否则就不是树形结构。

了解树的基本概念后,接下来就以这幅图来讲解树中的一些常见概念

节点的度:一个节点含有的子树的个数称为该节点的度,例如图中A的度为6

树的度:一棵树中,最大的节点的度,例如图中树的度为6

叶节点:度为0的节点称为叶节点,例如图中的B、C、H、I......

分支节点:度不为0的节点,例如图中:D、E、F、G...... 

父节点:一个节点含有子节点,则该节点为子节点的父节点,例如:D是H的父节点

子节点:与父节点相对,例如:H是D的子节点

二.二叉树的概念与实现

二叉树是树的一种,满足以下定义:

1.二叉树不存在度大于2的节点

2.二叉树的子树有左右之分,次序不能进行颠倒,二叉树是有序树

同样,二叉树也具有特殊形态,那就是完全二叉树和满二叉树。

完全二叉树: 每一层的节点填满以后再进行下一层填入,且每层的填入都是从左到右依次进行,这是一种相当有序的存在,是效率很高的数据结构。

满二叉树:特殊的完全的二叉树,每一层的节点个数都达到最大值。

 二叉树具有的性质(规定根节点的层数为1):

1.一颗非空二叉树的第n层上最多具有2^(n-1)个节点

2.深度为h的二叉树的最大节点个数为2^h-1

3.对于任何一个二叉树,度为0的节点个数(N0)等于度为2节点个数(N2)加1,即:N0=N2+1 

4.对于下标为i的节点,它的父节点下标为(i-1)/2,它的左孩子下标为2i+1,右孩子为2i+2(如果存在的话)

二叉树的存储结构可以分为顺序结构链式结构,但是此处我们只讨论顺序结构,使用顺序结构来实现堆。 如下图所示,使用顺序结构(数组)储存二叉树适合于完全二叉树,否则会造成数组空间的浪费。

 

三.堆的概念和结构

堆满足以下定义:

1.堆总是一颗完全二叉树

2.堆中的某个节点的值总是不大于或不小于其父节点的值

如下图所示:就是典型的大堆和小堆,但需要注意一点:大堆在储存在数组中不一定是降序排列,因为左右孩子节点的大小并没有关系,例如下图中80的左右孩子节点可以交换,同样满足大堆,但就不符合升序了,小堆也是同理。

四.堆的实现

1.向下调整算法

向下调整算法有一个前提:左右子树必须是一个堆。

如下图所示,除了根节点27以外,左右子树都是小堆,那么只需要将27进行向下调整就能使整个二叉树称为堆的结构。如何进行调整?要调整为小堆,27需要和左右孩子中较小的一个进行比较,图中是15,因此27需要先和15进行交换,这样才能满足小堆的结构,但是这还不够,27还要再向下一层进行比较调整,直到找到合适位置或称为叶节点。下图展现了整个过程:

以下是向下调整算法的代码实现,其中a是堆的数组实现,n是数组大小,parent是调整开始的节点,即父节点,根据二叉树性质得到其左孩子为:parent*2+1,但可能还有另外一个右孩子且大小不确定,因此进行判断,后续进行循环判断交换即可。 

  1. void AdjustDown(HPDatatype* a, int n, int parent)
  2. {
  3. int child = parent * 2 + 1;
  4. //找出孩子节点中大的一个(建大堆)
  5. if (child + 1 < n && a[child] > a[child + 1])
  6. {
  7. child++;
  8. }
  9. //直到超出数组范围n为止
  10. while (child < n)
  11. {
  12. if (a[child] < a[parent])
  13. {
  14. Swap(&a[child], &a[parent]);
  15. parent = child;
  16. child = parent * 2 + 1;
  17. }
  18. else
  19. {
  20. break;
  21. }
  22. }
  23. }

 

2. 堆的创建

有了向下调整算法,就下来就能进行建堆了。给定一个数组,不妨将其想象为一个二叉树的结构,要想使整个树成为堆,自然需要调整。如何调整?向下调整需要左右子树为堆的前提,在一个乱序的树中怎么找到堆?这里不妨直接将叶节点看作一个已经建立好的堆,单个的叶节点没有调整的必要,那么从叶节点的父节点开始调整,这样就能建成一个堆,如图中(5,10,11),随后从4开始调整,又有了(4,8,9)这一个堆,有了这两个堆,就又可以从2开始调整,这样(2,4,5,8,9,10,11)都是一个堆了,如此循环往复,最终就能将一个无序的数组调整为一个堆了。

 向下调整建堆非常简单,就是在向下调整算法中加个循环而已,不过需要强调,叶节点不需要进行向下调整,因此起点从最后一个节点的父节点开始即可(上图右体现),那么最后此处k-1是最后一个节点的下标,再-1进行/2就是得到其父节点,随后往后挨个进行调整即可。

  1. //向下调整建堆,k是数组大小
  2. for (int i = (k - 1 - 1) / 2; i < k; i++)
  3. {
  4. AdjustDown(a, k, i);
  5. }

3.向上调整算法

如果要向一个堆进行插入数据,此时就需要向上调整算法,此时只需要不断找到父节点进行比较即可,终止条件是找到最顶层的根节点比较后。

 

  1. //向上调整算法
  2. void AdjustUp(HPDatatype* a, int child)
  3. {
  4. int parent = (child - 1) / 2;
  5. while (child > 0)
  6. {
  7. if (a[child] < a[parent])
  8. {
  9. swap(&a[child], &a[parent]);
  10. child = parent;
  11. parent = (child - 1) / 2;
  12. }
  13. else
  14. {
  15. break;
  16. }
  17. }
  18. }

 4.堆的删除

删除堆的最后一个节点十分简单,直接删除该数据(让size--)即可。此处讨论的是删除根节点,删除后仍要使剩余数据成为堆。难点在于,如果直接删除根节点,其余节点前移,这样就会破坏原有的关系,原本的孩子节点可能就突然成为跟原本父节点同一层的了,关系全部就打乱了,再恢复就会很麻烦。

那么使用向下调整就会很轻松,交换最后一个节点和根节点,删除最后一个节点,现在的新根节点就是原本的最后一个节点,此时其余的关系仍然不变,即新根节点的左右都是堆的结构,满足向下调整的前提,那么执行向下调整算法一次,就能使成为新的堆。

 

五.堆排序

利用堆来进行排序分为两步:

1.利用向下调整进行建堆,其中排升序就建大堆,排降序就建小堆

2.利用堆删除的思想,将堆顶数据(最大或最小)与最后进行交换,再进行向下调整(除开最后一个已经是最大/最小的数据),这样下一次的堆顶就是第二大/第二小的数据了,反复进行就能排升序/降序了

  1. void HeapSort(int* a, int n)
  2. {
  3. //倒序:建小堆
  4. //向下调整建堆
  5. //从最后一个节点(n-1)的父节点开始
  6. for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  7. {
  8. AdjustDown(a, n, i);
  9. }
  10. //n-1是最后一个元素的下标
  11. int end = n - 1;
  12. while (end > 0)
  13. {
  14. //此时a[0]最小,放最后,再调整又成新的小堆,a[0]成第二小的
  15. swap(&a[0], &a[end]);
  16. AdjustDown(a, end, 0);
  17. end--;
  18. }
  19. }

六.堆-源码 

头文件:Heap.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<stdbool.h>
  5. #include<assert.h>
  6. typedef int HPDatatype;
  7. typedef struct Heap
  8. {
  9. HPDatatype* a;
  10. int size;
  11. int capacity;
  12. }HP;
  13. void HPInit(HP* php);
  14. void HPDestroy(HP* php);
  15. void HPPush(HP* php, HPDatatype x);
  16. void HPPop(HP* php);
  17. HPDatatype HPTop(HP* php);
  18. int HPEmpty(HP* php);
  19. int HPSize(HP* php);
  20. void swap(HPDatatype* p1, HPDatatype* p2);
  21. void HeapSort(int* a, int n);

源文件:Heap.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Heap.h"
  3. void HPInit(HP* php)
  4. {
  5. assert(php);
  6. php->a = NULL;
  7. php->capacity = php->size = 0;
  8. }
  9. void HPDestroy(HP* php)
  10. {
  11. assert(php);
  12. free(php->a);
  13. php->a = NULL;
  14. php->capacity = php->size = 0;
  15. }
  16. void swap(HPDatatype* p1, HPDatatype* p2)
  17. {
  18. HPDatatype tmp = *p1;
  19. *p1 = *p2;
  20. *p2 = tmp;
  21. }
  22. void AdjustUp(HPDatatype* a, int child)
  23. {
  24. int parent = (child - 1) / 2;
  25. while (child > 0)
  26. {
  27. if (a[child] < a[parent])
  28. {
  29. swap(&a[child], &a[parent]);
  30. child = parent;
  31. parent = (child - 1) / 2;
  32. }
  33. else
  34. {
  35. break;
  36. }
  37. }
  38. }
  39. void HPPush(HP* php, HPDatatype x)
  40. {
  41. assert(php);
  42. //扩容
  43. if (php->capacity == php->size)
  44. {
  45. int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
  46. HPDatatype* tmp = (HPDatatype*)realloc(php->a, sizeof(HPDatatype) * newcapacity);
  47. if (tmp == NULL)
  48. {
  49. perror("realloc fail");
  50. return;
  51. }
  52. php->a = tmp;
  53. php->capacity = newcapacity;
  54. }
  55. php->a[php->size] = x;
  56. php->size++;
  57. AdjustUp(php->a, php->size - 1);
  58. }
  59. //n是元素个数,即最大访问到n-1
  60. void AdjustDown(HPDatatype* a, int n, int parent)
  61. {
  62. int child = parent / 2 + 1;
  63. while (child < n)
  64. {
  65. //child+1可能造成数组越界访问
  66. //只有一个左孩子就不进行++
  67. if (child + 1 < n && a[child] > a[child + 1])
  68. {
  69. child++;
  70. }
  71. if (a[parent] > a[child])
  72. {
  73. swap(&a[parent], &a[child]);
  74. child = parent;
  75. parent = (parent - 1) / 2;
  76. }
  77. else
  78. {
  79. break;
  80. }
  81. }
  82. }
  83. void HPPop(HP* php)
  84. {
  85. assert(php);
  86. assert(php->size > 0);
  87. swap(&php->a[0], &php->a[php->size-1]);
  88. php->size--;
  89. AdjustDown(php->a, php->size, 0);
  90. }
  91. HPDatatype HPTop(HP* php)
  92. {
  93. assert(php);
  94. assert(php->size > 0);
  95. return php->a[0];
  96. }
  97. int HPEmpty(HP* php)
  98. {
  99. assert(php);
  100. return (php->size == 0);
  101. }
  102. int HPSize(HP* php)
  103. {
  104. assert(php);
  105. return php->size;
  106. }
  107. void HeapSort(int* a, int n)
  108. {
  109. //倒序:建小堆
  110. //向上调整建堆:相当于一个个进行插入
  111. /*for (int i = 1; i < n; i++)
  112. {
  113. AdjustUp(a, i);
  114. }*/
  115. //向下调整建堆
  116. //从最后一个节点(n-1)的父节点开始
  117. for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  118. {
  119. AdjustDown(a, n, i);
  120. }
  121. //n-1是最后一个元素的下标
  122. int end = n - 1;
  123. while (end > 0)
  124. {
  125. //此时a[0]最小,放最后,再调整又成新的小堆,a[0]成第二小的
  126. swap(&a[0], &a[end]);
  127. AdjustDown(a, end, 0);
  128. end--;
  129. }
  130. }

源文件:Test.c 

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Heap.h"
  3. void testHeap()
  4. {
  5. int a[] = { 4,6,7,8,9,1,2,3 };
  6. HP hp;
  7. HPInit(&hp);
  8. for (int i = 0; i < sizeof(a)/sizeof(int); i++)
  9. {
  10. HPPush(&hp, a[i]);
  11. }
  12. HPPop(&hp);
  13. HPPop(&hp);
  14. HPDestroy(&hp);
  15. }
  16. void testHeapsort()
  17. {
  18. int a[] = { 4,5,6,7,1,2,3,9,8 };
  19. HeapSort(a, sizeof(a) / sizeof(a[0]));
  20. }
  21. int main()
  22. {
  23. //testHeap();
  24. testHeapsort();
  25. return 0;
  26. }

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号