devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构详解——堆_c++堆

作者：我家小花儿 | 2024-05-16 12:45:04

赞

踩

c++堆

目录

1.堆的原理精讲

2.在数组中快速创建堆

3.堆的算法实现

4.插入元素 与弹出最大元素

4.1插入元素  

 4.2弹出最大元素  

5.堆的实际开发应用案例

5.1优先队列

5.2堆排序

6.堆实现及其功能完整代码

1.堆的原理精讲

最大堆特点：

当然，也有最小堆，最小堆就是将最大堆反过来，根结点为最小值~

堆是树中最有个性的树，他是用数组表示的树 。

2.在数组中快速创建堆

 1.首先我们需要找到最后一个结点的父结点如图(a),我们找到的结点是 87，然后找出该结点的最大子节点与自己比较，若该子节点比自身大，则将两个结点交换。
图(a)中，87 比左子节点 95 小,则交换之。如图(b)所示

2.我们移动到第一步前一个父节点 93，如图(c)所示.同理做第一步的比较操作，结果不需要交换。

 3.继续移动结点到前一个父结点 82,如图(d)所示,82 小于右子节点 95，则 82 与 95 交换,如图(e)所示，82 交换后，其值小于左子节点，不符合最大堆的特点，故需要继续向下调整，如图(f)所示。

 4.所有节点交换完毕,最大堆构建完成~

3.堆的算法实现

堆数据结构的定义： 

  1. #define DEFAULT_CAPACITY 128
  2. typedef struct _Heap {
  3. 	int* arr;		//存储堆元素的数组
  4. 	int size;		//当前已存储的元素个数
  5. 	int capacity;	//当前的存储容量
  6. }Heap;

建立最大堆算法：  

  1. bool initHeap(Heap& heap, int* original, int size);
  2. static void buildHeap(Heap& heap);
  3. static void adjustDown(Heap& heap, int index);
  4.  
  5. //初始化堆
  6. bool initHeap(Heap& heap, int* original, int size) {
  7. 	//如果默认大小比size小，则申请默认大小的空间，否则申请size大小的空间
  8. 	int capacity = DEFAULT_CAPACITY > size ? DEFAULT_CAPACITY : size;
  9. 	heap.arr = new int[capacity];
  10. 	if (!heap.arr)return false;
  11. 	heap.capacity = capacity;
  12. 	heap.size = 0;
  13. 	//如果存在原始数据，则拷贝过来
  14. 	if (size > 0) {
  15. 		memcpy(heap.arr, original, size * sizeof(int));
  16. 		heap.size = size;
  17. 		buildHeap(heap);
  18. 	}
  19. 	return true;
  20. }
  21.  
  22. /*从最后一个父节点开始（heap.size) - 1 / 2）（因为size是从1开始，所以要先减去1）
  23. 逐个调整所有的父节点（直到根节点），确保每一个父节点都是最大堆，最后
  24. 整体上形成一个最大堆*/
  25. void buildHeap(Heap& heap) {
  26. 	for (int i = (heap.size - 1) / 2; i >= 0; i--) {
  27. 		adjustDown(heap, i);
  28. 	}
  29. }
  30.  
  31. void adjustDown(Heap& heap, int index) {
  32. 	int cur = heap.arr[index];  //记录父节点值
  33. 	int parent, child;
  34.  
  35. 	/*怕段是否存在大于当前结点的子节点，如果不存在，则堆本身平衡，不需要
  36. 	调整，如果存在，则将最大子节点与之交换，交换后，如果这个子节点还有
  37. 	子节点（即parent*2+1<heap.size 成立）则要按照相同步骤对这个子节点进行
  38. 	调整*/
  39. 	for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
  40. 		child = parent * 2 + 1; //左子节点
  41.  
  42. 		//取两个子节点最大结点
  43. 		if (((child + 1) < heap.size) && (heap.arr[child + 1] > heap.arr[child])) {
  44. 			child++;
  45. 		}
  46. 		if (cur >= heap.arr[child])break;//不大于，跳出循环
  47. 		else {
  48. 			/*大于当前父节点，进行交换，然后从子节点位置继续向下调整，
  49. 			即for从第二次循环开始，初始值都为上一次的子节点位置*/
  50. 			heap.arr[parent] = heap.arr[child];
  51. 			heap.arr[child] = cur;
  52. 		}
  53. 	}
  54. }

完成测试代码 ：

  1. int main() {
  2.  
  3. 	Heap hp;
  4. 	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
  5.  
  6. 	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
  7. 		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
  8. 		exit(-1);
  9. 	}
  10.  
  11. 	for (int i = 0; i < hp.size; i++) {
  12. 		cout << hp.arr[i] << endl;
  13. 	}
  14. 	system("pause");
  15. 	return 0;
  16. }

运行结果：

知识点补充：

1.memcpy(内存拷贝函数)

memcpy函数的功能是从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。用于double、int、结构体等

  1. double arryDouble_Src[16];
  2. double arryDouble_Det[16];
  3.  
  4. memcpy( arryDouble_Det, arryDouble_Src, sizeof(double)*16);
  1. int arryInt_Src[16];
  2. int arryInt_Dst[16];
  3.  
  4. memcpy( arryInt_Dst, arryInt_Src, sizeof(int)*16);
  1. struct DataNum
  2. {
  3. 	int Data0;
  4. 	int Data1;
  5. }
  6.  
  7. DataNum arryStruct_Src[16];
  8. DataNum arryStruct_Dst[16];
  9.  
  10. memcpy( arryStruct_Dst, arryStruct_Src, sizeof(DataNum )*16);

2. 在一般的函数前面加上static

加了static后表示该函数失去了全局可见性，只在该函数所在作用域内可见。

当函数声明为static以后，编译器在该目标编译单元内只含有该函数入口地址，没有函数名，其它编译器便不能通过该函数名调用该函数。

4.插入元素 与弹出最大元素

4.1插入元素  

将数字99插入到下面最大堆中

 对应的数组：{95, 93, 87, 92, 86, 82}

将新进的元素插入到大顶堆的尾部,如下图 b 所示: 

对应的数组：{95, 93, 87, 92, 86, 82, 99} 

此时最大堆已经被破坏，需要重新调整, 因加入的节点比父节点大，则新节点跟父节点调换即可,如图 c所示；调整后，新节点如果比新的父节点小，则已经调整到位，如果比新的父节点大，则需要和父节点重新进行交换，如图 d, 至此，最大堆调整完成。 

 代码实现：

  1. static bool insertHeap(Heap& heap, int value);
  2. static void adjustUp(Heap& heap, int index);
  3.  
  4. bool insertHeap(Heap& heap, int value) {
  5. 	if (heap.size == heap.capacity) {
  6. 		fprintf(stderr, "栈空间耗尽!\n");
  7. 		return false;
  8. 	}
  9.  
  10. 	int index = heap.size;
  11. 	heap.arr[heap.size++] = value;//先赋值value，再size++
  12. 	adjustUp(heap, index);
  13. }
  14.  
  15. void adjustUp(Heap& heap, int index) {
  16. 	if (index < 0 || index >= heap.size) {
  17. 		//如果只有一个结点（插入的结点）inedx<0，或者大于堆的最大值，return掉
  18. 		return;
  19. 	}
  20. 	int temp = heap.arr[index];//temp为插入的值
  21. 	while (index > 0) {
  22. 		
  23. 		int parent = (index - 1) / 2;
  24. 		if (parent >= 0) {   //如果索引没有出界，就执行想要操作
  25. 			if (heap.arr[parent] < temp) {
  26. 				heap.arr[index] = heap.arr[parent];
  27. 				heap.arr[parent] = temp;
  28. 				index = parent;
  29. 			}
  30. 			else break;    //如果没有比父结点大，则跳出
  31. 		}
  32. 		else break;  //越界，结束循环
  33. 	}
  34. }

完成测试代码 ： 

  1. int main() {
  2.  
  3. 	Heap hp;
  4. 	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
  5.  
  6. 	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
  7. 		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
  8. 		exit(-1);
  9. 	}
  10.  
  11. 	for (int i = 0; i < hp.size; i++) {
  12. 		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
  13. 	}
  14.  
  15. 	insertHeap(hp, 99);
  16. 	printf("在堆中插入新的元素99，插入结果：\n");
  17. 	for (int i = 0; i < hp.size; i++) {
  18. 		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
  19. 	}
  20. 	system("pause");
  21. 	return 0;
  22. }

运行结果：

当实现了插入功能后，对于堆的初始建立就有了两种方法。第一种就是直接将数组传入，第二种则是将元素一个个插入。相比较而言，对于一个个插入的方法比较次数更少，效率更高~ 

 4.2弹出最大元素  

 如果我们将堆顶的元素删除，那么顶部有一个空的节点，怎么处理？

当插入节点的时候，我们将新的值插入数组的尾部。现在我们来做相反的事情：我们取出数组中的最后一个元素，将它放到堆的顶部，然后再修复堆属性。 

  1. static bool popMax(Heap& heap, int& value);
  2. bool popMax(Heap& heap, int& value) {
  3. 	if (heap.size < 1)return false;
  4. 	value = heap.arr[0];
  5.  
  6. 	//将size-1的位置值赋给根节点，size本身又--
  7. 	/*相当于
  8. 		heap.arr[0] = heap.arr[heap.size-1];
  9. 		heap.size--;
  10. 	*/
  11. 	heap.arr[0] = heap.arr[--heap.size];
  12. 	adjustDown(heap, 0);  //向下执行堆调整
  13. 	return true;
  14. }

完成测试代码 ： 

  1. int main() {
  2.  
  3. 	Heap hp;
  4. 	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
  5.  
  6. 	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
  7. 		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
  8. 		exit(-1);
  9. 	}
  10.  
  11. 	for (int i = 0; i < hp.size; i++) {
  12. 		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
  13. 	}
  14.  
  15. 	/*向堆中插入元素
  16. 	insertHeap(hp, 99);
  17. 	printf("在堆中插入新的元素99，插入结果：\n");
  18. 	for (int i = 0; i < hp.size; i++) {
  19. 		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
  20. 	}*/
  21.  
  22. 	int value;
  23. 	while (popMax(hp, value)) {
  24. 		cout << "依次出列最大元素：" << value << endl;
  25. 	}	
  26. 	
  27. 	system("pause");
  28. 	return 0;
  29. }

运行结果：   

 

使用堆方法依次弹出最大值，执行效率高于冒泡排序~

5.堆的实际开发应用案例

5.1优先队列

 操作系统内核作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

 

如果最小键值元素拥有最高的优先级，那么这种优先队列叫作 升序优先队列（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作 降序优先队列（即总是先删除最大的元素）；由于这两种类型是完全对称的，所以只需要关注其中一种，如升序优先队列。

5.2堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。
(选择排序工作原理 -——第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零) 

核心排序如下：

 

6.堆实现及其功能完整代码

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define DEFAULT_CAPACITY 128
  5. typedef struct _Heap {
  6. 	int* arr;		//存储堆元素的数组
  7. 	int size;		//当前已存储的元素个数
  8. 	int capacity;	//当前的存储容量
  9. }Heap;
  10.  
  11.  
  12. bool initHeap(Heap& heap, int* original, int size);
  13. static void buildHeap(Heap& heap);
  14. static void adjustDown(Heap& heap, int index);
  15. static bool insertHeap(Heap& heap, int value);
  16. static void adjustUp(Heap& heap, int index);
  17. static bool popMax(Heap& heap, int& value);
  18.  
  19. //初始化堆
  20. bool initHeap(Heap& heap, int* original, int size) {
  21. 	//如果默认大小比size小，则申请默认大小的空间，否则申请size大小的空间
  22. 	int capacity = DEFAULT_CAPACITY > size ? DEFAULT_CAPACITY : size;
  23. 	heap.arr = new int[capacity];
  24. 	if (!heap.arr)return false;
  25. 	heap.capacity = capacity;
  26. 	heap.size = 0;
  27. 	//如果存在原始数据，则拷贝过来
  28. 	if (size > 0) {
  29. 		memcpy(heap.arr, original, size * sizeof(int));
  30. 		heap.size = size;
  31. 		buildHeap(heap);
  32. 	}
  33. 	return true;
  34. }
  35.  
  36. /*从最后一个父节点开始（heap.size) - 1 / 2）（因为size是从1开始，所以要先减去1）
  37. 逐个调整所有的父节点（直到根节点），确保每一个父节点都是最大堆，最后
  38. 整体上形成一个最大堆*/
  39. void buildHeap(Heap& heap) {
  40. 	for (int i = (heap.size - 1) / 2; i >= 0; i--) {
  41. 		adjustDown(heap, i);
  42. 	}
  43. }
  44.  
  45. void adjustDown(Heap& heap, int index) {
  46. 	int cur = heap.arr[index];  //记录父节点值
  47. 	int parent, child;
  48.  
  49. 	/*怕段是否存在大于当前结点的子节点，如果不存在，则堆本身平衡，不需要
  50. 	调整，如果存在，则将最大子节点与之交换，交换后，如果这个子节点还有
  51. 	子节点（即parent*2+1<heap.size 成立）则要按照相同步骤对这个子节点进行
  52. 	调整*/
  53. 	for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
  54. 		child = parent * 2 + 1; //左子节点
  55.  
  56. 		//取两个子节点最大结点
  57. 		if (((child + 1) < heap.size) && (heap.arr[child + 1] > heap.arr[child])) {
  58. 			child++;
  59. 		}
  60. 		if (cur >= heap.arr[child])break;//不大于，跳出循环
  61. 		else {
  62. 			/*大于当前父节点，进行交换，然后从子节点位置继续向下调整，
  63. 			即for从第二次循环开始，初始值都为上一次的子节点位置*/
  64. 			heap.arr[parent] = heap.arr[child];
  65. 			heap.arr[child] = cur;
  66. 		}
  67. 	}
  68. }
  69. static bool popMax(Heap& heap, int& value);
  70. bool popMax(Heap& heap, int& value) {
  71. 	if (heap.size < 1)return false;
  72. 	value = heap.arr[0];
  73.  
  74. 	//将size-1的位置值赋给根节点，size本身又--
  75. 	/*相当于
  76. 		heap.arr[0] = heap.arr[heap.size-1];
  77. 		heap.size--;
  78. 	*/
  79. 	heap.arr[0] = heap.arr[--heap.size];
  80. 	adjustDown(heap, 0);  //向下执行堆调整
  81. 	return true;
  82. }
  83.  
  84.  
  85. bool insertHeap(Heap& heap, int value) {
  86. 	if (heap.size == heap.capacity) {
  87. 		fprintf(stderr, "栈空间耗尽!\n");
  88. 		return false;
  89. 	}
  90.  
  91. 	int index = heap.size;
  92. 	heap.arr[heap.size++] = value;//先赋值value，再size++
  93. 	adjustUp(heap, index);
  94. }
  95.  
  96. void adjustUp(Heap& heap, int index) {
  97. 	if (index < 0 || index >= heap.size) {
  98. 		//如果只有一个结点（插入的结点）inedx<0，或者大于堆的最大值，return掉
  99. 		return;
  100. 	}
  101. 	int temp = heap.arr[index];//temp为插入的值
  102. 	while (index > 0) {
  103. 		
  104. 		int parent = (index - 1) / 2;
  105. 		if (parent >= 0) {   //如果索引没有出界，就执行想要操作
  106. 			if (heap.arr[parent] < temp) {
  107. 				heap.arr[index] = heap.arr[parent];
  108. 				heap.arr[parent] = temp;
  109. 				index = parent;
  110. 			}
  111. 			else break;    //如果没有比父结点大，则跳出
  112. 		}
  113. 		else break;  //越界，结束循环
  114. 	}
  115. }
  116.  
  117.  
  118.  
  119. int main() {
  120.  
  121. 	Heap hp;
  122. 	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
  123.  
  124. 	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
  125. 		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
  126. 		exit(-1);
  127. 	}
  128.  
  129. 	for (int i = 0; i < hp.size; i++) {
  130. 		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
  131. 	}
  132.  
  133. 	//向堆中插入元素
  134. 	insertHeap(hp, 99);
  135. 	printf("在堆中插入新的元素99，插入结果：\n");
  136. 	for (int i = 0; i < hp.size; i++) {
  137. 		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
  138. 	}
  139.  
  140. 	int value;
  141. 	while (popMax(hp, value)) {
  142. 		cout << "依次出列最大元素：" << value << endl;
  143. 	}	
  144. 	
  145. 	system("pause");
  146. 	return 0;
  147. }
  148.  
  149.

运行截图：

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号