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

数据结构：大顶堆、小顶堆

作者：知新_RL | 2024-05-25 17:50:00

赞

踩

小顶堆

前言：

       堆是其中一种非常重要且实用的数据结构。堆可以用于实现优先队列，进行堆排序，以及解决各种与查找和排序相关的问题。本文将深入探讨两种常见的堆结构：大顶堆和小顶堆，并通过 C++ 语言展示如何实现和使用它们。

1. 什么是大顶堆和小顶堆？

前提：

        堆是一种完全二叉树。完全二叉树的定义：所有节点从上往下，从左往右的依次排列，不能有空位置，是为完全二叉树。

        下面是完全二叉树和不完全二叉树的示意图：

在这里插入图片描述

大顶堆：

        根节点（堆顶元素）是所有节点中的最大值（父节点都大于左右子节点）。大顶堆常用于实现优先队列，且可用于构建堆排序算法。

小顶堆：

        小顶堆中的根节点是所有节点中的最小值（父节点都小于左右子节点）。小顶堆常用于问题如：查找流中的前 K 个最小元素。

示意图：
在这里插入图片描述

2. 大小顶堆的底层实现

        一般来说，定义二叉树都是定义一个节点类，节点类中包含本节点的数据元素和两个节点指针，分别指向左右子节点，通过这两个节点指针将整个树节点连起来。

代码：

  1. template <typename Type>
  2. class BstNode
  3. {
  4. public:
  5. 	BstNode():leftChild(nullptr), rightChild(nullptr){};
  6. 	BstNode(Type _content) :leftChild(nullptr), rightChild(nullptr)
  7. 	{
  8. 		content = _content;
  9. 	};
  10. private:
  11. 	Type content;
  12. 	BstNode<Type> *leftChild;
  13. 	BstNode<Type> *rightChild;
  14. };

         实际上，堆一般用数组表示，如下图。究其原因，我认为的是通过节点类的方式占用的内存空间多，多加了两个指针。并且当我们做插入操作向上渗透时，需要找到节点的父节点(文章后面会详细描述)，这样实际的节点应该再加一个标识父节点的指针。这样实际是多了3个指针。

图示： 

3. 代码实现小顶堆

3.1 定义小顶堆类

  1. template<typename T>
  2. class MinHeap
  3. {
  4. public:
  5. 	MinHeap(int _maxsize = 10);
  6. 	~MinHeap();
  7.  
  8. 	void Push(T _data);//插入数据
  9. 	void Pop();//删除堆顶数据
  10. 	T& Top();//获取堆顶数据
  11.  
  12. 	void ShowHeap();//打印堆
  13. private:
  14. 	T *heap;
  15. 	int MaxSize;//堆数组的最大大小
  16. 	int currentSize;//堆数组当前大小
  17. };

3.2 构造函数

  1. template<typename T>
  2. MinHeap<T>::MinHeap(int _maxsize)
  3. :MaxSize(_maxsize)
  4. {
  5. 	try{
  6. 		if (MaxSize < 1)
  7. 			throw "Error Size,< 1";
  8. 		heap = new T[MaxSize];
  9. 		currentSize = 0;
  10. 	}
  11. 	catch (const char* cp){
  12.  
  13. 		//1.提示用户错误信息，提示用户重新输入
  14. 		int size = 0;
  15. 		while (size < 1){
  16. 			std::cout << cp << std::endl;
  17. 			std::cout << "please Enter size again" << std::endl;
  18. 			std::cin >> size;
  19. 		}
  20.  
  21. 		//2.初始化MinHeap类的数据成员
  22. 		MaxSize = size;
  23. 		heap = new T[MaxSize];
  24. 		currentSize = 0;
  25. 	}
  26. }

        解释：这里我做了异常处理。当堆数组的大小MaxSize<1时，抛出异常，并提示输入大小，一直到输入的大小>=1。

3.3 插入

插入方法：
  1. 首先将需插入的数据放在堆的最后一个位置
  2. 然后依次和父节点比较，比父节点小就和父节点交换，再向上比较；比父节点大就停止比较。

比如我按20->30->15->10->9->8->12依次插入，插入示意图如下：

在这里插入图片描述

代码入下：
  1. template<typename T>
  2. void MinHeap<T>::Push(T _data)
  3. {
  4. 	if (currentSize == MaxSize){
  5. 		//堆满了，扩容
  6. 	}
  7. 	//将数据放入最后一个位置
  8. 	//注意：currentSize和数组索引值差1：
  9. 	//比如currentSize = 3，对应的数组索引为2
  10. 	//所以，当currentSize=3时，即堆数组有3个数据时，新插入的数据应在数组索引3上
  11. 	heap[currentSize] = _data;
  12.  
  13. 	int sonIndex = currentSize;//最后一个位置的数组索引
  14. 	int fatherIndex = (currentSize - 1)/ 2;//最后一个位置的父节点的数组索引
  15.  
  16. 	while (sonIndex > 0){
  17. 		if (heap[sonIndex] < heap[fatherIndex]){
  18. 			std::swap(heap[sonIndex], heap[fatherIndex]);//交换父子节点元素
  19. 			
  20. 			//继续向上
  21. 			sonIndex = fatherIndex;
  22. 			fatherIndex = (fatherIndex - 1) / 2;
  23. 		}
  24. 		else break;
  25. 	}
  26.  
  27. 	currentSize++;//堆数组当前大小加1
  28. }

        currentSize表示的是当前堆数组有多少个元素。如下图，比如currentSize = 3，表明当前有3个数据。再push一个数据时，在数组的存储的位置刚好是索引3。

示意图：

        如下图，节点7和节点4的父节点都是节点2。节点7的索引为1，节点4索引为2，节点2的索引为0，所以计算7 4 节点的父节点公式为==（索引-1）/2==，其他节点也一样。这里你不从数组索引角度，从树的层序角度也是一样，只不过公式要变为：层序号/2。

扩大堆数组容量
        在上述代码中，当currentSize == MaxSize时，表示堆数组已经满了，此时我们需要扩大数组的大小，这和循环队列和顺序栈是一样的原理。
循环队列：带你一步步用C++实现循环队列
顺序栈：用C++实现顺序栈(以数组为底层数据结构，可自动扩容。
代码如下：

  1. template<typename T>
  2. void MinHeap<T>::ChangeSize()
  3. {
  4. 	int size = MaxSize * 2;//堆数组容量扩大1倍
  5.  
  6. 	T* tmp = new T[size];//1.申请一块原来2倍大小的空间。
  7. 	std::copy(heap, heap + MaxSize, tmp);//2.将栈中的数据赋值到新的内存空间
  8. 	delete[] heap;//3.删除老的空间
  9.  
  10. 	heap = tmp;//4.heap指向新地址
  11. 	MaxSize = size;//5.改变MaxSize
  12. }

        注意：由于C++编译器是不检查数组越界的，所以，即使程序员不自己扩容，使用越界的索引程序也不会报错，只是它会继续向下占用一块内存。程序员必须注意数组越界的问题。

3.4 删除

删除步骤：
  1. 首先把堆顶元素删除
  2. 接着把堆的最后一个数据放在堆顶
  3. 最后把堆顶数据向下渗透，不断的和两个子节点比较，若父节点不比两个子节点的任意一个小，取两个子节点中小的和父节点交换，一直这样下去，直到父节点比左右子节点都小。
示意图：

在这里插入图片描述

代码如下：
  1. template<typename T>
  2. void MinHeap<T>::Pop()
  3. {
  4. 	if (currentSize == 0){
  5. 		std::cout << "Error!The heap is empty，Invalid operation." << std::endl;
  6. 		return;
  7. 	}
  8.  
  9. 	heap[0] = heap[--currentSize];//删除堆顶，并将最后一个数据放在堆顶
  10.  
  11. 	int fatherIndex = 0;//父节点索引为堆顶
  12. 	int leftSonIndex = fatherIndex * 2 + 1;//获得左子节点索引
  13. 	int RightSonIndex = leftSonIndex + 1;//获得右子节点索引
  14.  
  15. 	//确认循环条件
  16. 	while (leftSonIndex < currentSize ){
  17. 		/**1.找左右子节点中最小值的数组索引***/
  18. 		int minIndex;
  19. 		//如果RightSonIndex < currentSize,表明fatherIndex有右子节点
  20. 		if (RightSonIndex < currentSize){
  21. 			minIndex = heap[leftSonIndex] > heap[RightSonIndex] ?  RightSonIndex: leftSonIndex;
  22. 		}
  23. 		else{
  24. 			minIndex = leftSonIndex;
  25. 		}
  26.  
  27. 		/**2.父节点大就交换，否则退出循环***/
  28. 		if (heap[fatherIndex] > heap[minIndex])
  29. 			std::swap(heap[fatherIndex], heap[minIndex]);
  30. 		else break;
  31.  
  32. 		fatherIndex = minIndex;
  33. 		leftSonIndex = fatherIndex * 2 + 1;
  34. 		RightSonIndex = leftSonIndex + 1;
  35. 	}
  36. }

对于while循环条件说明：
        使用左子节点leftSonIndex和currentSize比较，不要使用右子节点RightSonIndex，因为右子节点RightSonIndex可能没有。当然，你也可以使用父节点fatherIndex和currentSize比较：fatherIndex<currentSize/2。
验证循环的真确性，只需考虑以下三种情况，大家可自行验证。


析构函数：
        析构只需将申请的内存释放即可。

  1. template<typename T>
  2. MinHeap<T>::~MinHeap()
  3. {
  4. 	delete []heap; 
  5. }

4. 代码实现大顶堆

        原理和小顶堆一样，直接给出代码

  1. #ifndef _MAX_HEAP_H
  2. #define _MAX_HEAP_H
  3.  
  4. template<typename T>
  5. class MaxHeap
  6. {
  7. public:
  8. 	MaxHeap(int _maxsize = 10);
  9. 	~MaxHeap();
  10.  
  11. 	void Push(T _data);//插入数据
  12. 	void Pop();//删除堆顶数据
  13. 	T& Top();//获取堆顶数据
  14.  
  15. 	void ShowHeap();
  16. private:
  17. 	T *heap;
  18. 	int MaxSize;//堆数组的最大大小
  19. 	int currentSize;//堆数组当前大小
  20.  
  21. 	void ChangeSize();//扩大堆数组的大小
  22. };
  23.  
  24. template<typename T>
  25. MaxHeap<T>::MaxHeap(int _maxsize)
  26. :MaxSize(_maxsize)
  27. {
  28. 	try{
  29. 		if (MaxSize < 1)
  30. 			throw "Error Size,< 1";
  31. 		heap = new T[MaxSize];
  32. 		currentSize = 0;
  33. 	}
  34. 	catch (const char* cp){
  35.  
  36. 		//1.提示用户错误信息，提示用户重新输入
  37. 		int size = 0;
  38. 		while (size < 1){
  39. 			std::cout << cp << std::endl;
  40. 			std::cout << "please Enter size again" << std::endl;
  41. 			std::cin >> size;
  42. 		}
  43.  
  44. 		//2.初始化MaxHeap类的数据成员
  45. 		MaxSize = size;
  46. 		heap = new T[MaxSize];
  47. 		currentSize = 0;
  48. 	}
  49. }
  50. template<typename T>
  51. MaxHeap<T>::~MaxHeap()
  52. {
  53. 	delete[]heap;
  54. }
  55. template<typename T>
  56. void MaxHeap<T>::Push(T _data)
  57. {
  58. 	if (currentSize == MaxSize){
  59. 		//堆满了，扩容
  60. 		ChangeSize();
  61. 	}
  62. 	//将数据放入最后一个位置
  63. 	//注意：currentSize和数组索引值差1：
  64. 	//比如currentSize = 3，对应的数组索引为2
  65. 	//所以，当currentSize=3时，即堆数组有3个数据时，新插入的数据应在数组索引3上
  66. 	heap[currentSize] = _data;
  67.  
  68. 	int sonIndex = currentSize;//最后一个位置的数组索引
  69. 	int fatherIndex = (currentSize - 1) / 2;//最后一个位置的父节点的数组索引
  70.  
  71. 	while (sonIndex > 0){
  72. 		if (heap[sonIndex] > heap[fatherIndex]){
  73. 			std::swap(heap[sonIndex], heap[fatherIndex]);
  74.  
  75. 			//继续向上
  76. 			sonIndex = fatherIndex;
  77. 			fatherIndex = (fatherIndex - 1) / 2;
  78. 		}
  79. 		else break;
  80. 	}
  81.  
  82. 	currentSize++;
  83. }
  84. template<typename T>
  85. void MaxHeap<T>::Pop()
  86. {
  87. 	if (currentSize == 0){
  88. 		std::cout << "Error!The heap is empty，Invalid operation." << std::endl;
  89. 		return;
  90. 	}
  91.  
  92. 	heap[0] = heap[--currentSize];//删除堆顶，并将最后一个数据放在堆顶
  93.  
  94. 	int fatherIndex = 0;//父节点索引为堆顶
  95. 	int leftSonIndex = fatherIndex * 2 + 1;//获得左子节点索引
  96. 	int RightSonIndex = leftSonIndex + 1;//获得右子节点索引
  97.  
  98. 	//确认循环条件
  99. 	while (leftSonIndex < currentSize){
  100. 		/**1.找左右子节点中最小值的数组索引***/
  101. 		int maxIndex;
  102. 		//如果RightSonIndex < currentSize,表明fatherIndex有右子节点
  103. 		if (RightSonIndex < currentSize){
  104. 			maxIndex = heap[leftSonIndex] < heap[RightSonIndex] ? RightSonIndex : leftSonIndex;
  105. 		}
  106. 		else{
  107. 			maxIndex = leftSonIndex;
  108. 		}
  109.  
  110. 		/**2.父节点小就交换，否则退出循环***/
  111. 		if (heap[fatherIndex] < heap[maxIndex])
  112. 			std::swap(heap[fatherIndex], heap[maxIndex]);
  113. 		else break;
  114.  
  115. 		fatherIndex = maxIndex;
  116. 		leftSonIndex = fatherIndex * 2 + 1;
  117. 		RightSonIndex = leftSonIndex + 1;
  118. 	}
  119. }
  120. template<typename T>
  121. T& MaxHeap<T>::Top()
  122. {
  123. 	if (currentSize == 0)
  124. 		throw "Error.The heap is empty,there is not data.";
  125. 	return heap[0];
  126. }
  127.  
  128. template<typename T>
  129. void MaxHeap<T>::ChangeSize()
  130. {
  131. 	int size = MaxSize * 2;//堆数组容量扩大1倍
  132.  
  133. 	T* tmp = new T[size];//1.申请一块原来2倍大小的空间。
  134. 	std::copy(heap, heap + MaxSize, tmp);//2.将栈中的数据赋值到新的内存空间
  135. 	delete[] heap;//3.删除老的空间
  136.  
  137. 	heap = tmp;//4.heap指向新地址
  138. 	MaxSize = size;//5.改变MaxSize
  139. }
  140.  
  141. template<typename T>
  142. void MaxHeap<T>::ShowHeap()
  143. {
  144. 	int size = 1;
  145. 	for (int i = 0; i < currentSize;){
  146. 		std::cout << "[ ";
  147. 		for (int j = 0; j < size && i < currentSize; j++){
  148. 			std::cout << heap[i++] << " ";
  149. 		}
  150. 		std::cout << "]" << std::endl;
  151. 		size *= 2;
  152. 	}
  153. }
  154.  
  155. #endif

5. 测试

        下面只测试小顶堆，大顶堆可自行测试。

MinHeap.h

  1. #ifndef _MIN_HEAP_H
  2. #define _MIN_HEAP_H
  3.  
  4. template<typename T>
  5. class MinHeap
  6. {
  7. public:
  8. 	MinHeap(int _maxsize = 10);
  9. 	~MinHeap();
  10.  
  11. 	void Push(T _data);//插入数据
  12. 	void Pop();//删除堆顶数据
  13. 	T& Top();//获取堆顶数据
  14.  
  15. 	void ShowHeap();
  16. private:
  17. 	T *heap;
  18. 	int MaxSize;//堆数组的最大大小
  19. 	int currentSize;//堆数组当前大小
  20.  
  21. 	void ChangeSize();//扩大堆数组的大小
  22. };
  23.  
  24. template<typename T>
  25. MinHeap<T>::MinHeap(int _maxsize)
  26. :MaxSize(_maxsize)
  27. {
  28. 	try{
  29. 		if (MaxSize < 1)
  30. 			throw "Error Size,< 1";
  31. 		heap = new T[MaxSize];
  32. 		currentSize = 0;
  33. 	}
  34. 	catch (const char* cp){
  35.  
  36. 		//1.提示用户错误信息，提示用户重新输入
  37. 		int size = 0;
  38. 		while (size < 1){
  39. 			std::cout << cp << std::endl;
  40. 			std::cout << "please Enter size again" << std::endl;
  41. 			std::cin >> size;
  42. 		}
  43.  
  44. 		//2.初始化MinHeap类的数据成员
  45. 		MaxSize = size;
  46. 		heap = new T[MaxSize];
  47. 		currentSize = 0;
  48. 	}
  49. } 
  50. template<typename T>
  51. MinHeap<T>::~MinHeap()
  52. {
  53. 	delete []heap; 
  54. }
  55. template<typename T>
  56. void MinHeap<T>::Push(T _data)
  57. {
  58. 	if (currentSize == MaxSize){
  59. 		//堆满了，扩容
  60. 		ChangeSize();
  61. 	}
  62. 	//将数据放入最后一个位置
  63. 	//注意：currentSize和数组索引值差1：
  64. 	//比如currentSize = 3，对应的数组索引为2
  65. 	//所以，当currentSize=3时，即堆数组有3个数据时，新插入的数据应在数组索引3上
  66. 	heap[currentSize] = _data;
  67.  
  68. 	int sonIndex = currentSize;//最后一个位置的数组索引
  69. 	int fatherIndex = (currentSize - 1)/ 2;//最后一个位置的父节点的数组索引
  70. 	 
  71. 	while (sonIndex > 0){
  72. 		if (heap[sonIndex] < heap[fatherIndex]){
  73. 			std::swap(heap[sonIndex], heap[fatherIndex]);
  74. 			
  75. 			//继续向上
  76. 			sonIndex = fatherIndex;
  77. 			fatherIndex = (fatherIndex - 1) / 2;
  78. 		}
  79. 		else break;
  80. 	}
  81.  
  82. 	currentSize++;
  83. }
  84. template<typename T>
  85. void MinHeap<T>::Pop()
  86. {
  87. 	if (currentSize == 0){
  88. 		std::cout << "Error!The heap is empty，Invalid operation." << std::endl;
  89. 		return;
  90. 	}
  91.  
  92. 	heap[0] = heap[--currentSize];//删除堆顶，并将最后一个数据放在堆顶
  93.  
  94. 	int fatherIndex = 0;//父节点索引为堆顶
  95. 	int leftSonIndex = fatherIndex * 2 + 1;//获得左子节点索引
  96. 	int RightSonIndex = leftSonIndex + 1;//获得右子节点索引
  97.  
  98. 	//确认循环条件
  99. 	while (leftSonIndex < currentSize ){
  100. 		/**1.找左右子节点中最小值的数组索引***/
  101. 		int minIndex;
  102. 		//如果RightSonIndex < currentSize,表明fatherIndex有右子节点
  103. 		if (RightSonIndex < currentSize){
  104. 			minIndex = heap[leftSonIndex] > heap[RightSonIndex] ?  RightSonIndex: leftSonIndex;
  105. 		}
  106. 		else{
  107. 			minIndex = leftSonIndex;
  108. 		}
  109.  
  110. 		/**2.父节点大就交换，否则退出循环***/
  111. 		if (heap[fatherIndex] > heap[minIndex])
  112. 			std::swap(heap[fatherIndex], heap[minIndex]);
  113. 		else break;
  114.  
  115. 		fatherIndex = minIndex;
  116. 		leftSonIndex = fatherIndex * 2 + 1;
  117. 		RightSonIndex = leftSonIndex + 1;
  118. 	}
  119. }
  120. template<typename T>
  121. T& MinHeap<T>::Top()
  122. {
  123. 		if (currentSize == 0)
  124. 			throw "Error.The heap is empty,there is not data.";
  125. 		return heap[0];
  126. }
  127.  
  128. template<typename T>
  129. void MinHeap<T>::ChangeSize()
  130. {
  131. 	int size = MaxSize * 2;//堆数组容量扩大1倍
  132.  
  133. 	T* tmp = new T[size];//1.申请一块原来2倍大小的空间。
  134. 	std::copy(heap, heap + MaxSize, tmp);//2.将栈中的数据赋值到新的内存空间
  135. 	delete[] heap;//3.删除老的空间
  136.  
  137. 	heap = tmp;//4.heap指向新地址
  138. 	MaxSize = size;//5.改变MaxSize
  139. }
  140.  
  141. template<typename T>
  142. void MinHeap<T>::ShowHeap()
  143. {
  144. 	int size = 1;
  145. 	for (int i = 0; i < currentSize;){
  146. 		std::cout << "[ ";
  147. 		for (int j = 0; j < size && i < currentSize; j++){
  148. 			std::cout <<heap[i++] <<" ";
  149. 		}
  150. 		std::cout << "]"<<std::endl;
  151. 		size *= 2;
  152. 	}
  153. }
  154.  
  155. #endif

Main.cpp

  1. #include <iostream>
  2. #include "MinHeap.h"
  3. #include "MaxHeap.h"
  4.  
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9. 	MinHeap<int> a(4);
  10. 	
  11. 	/*************插入***********/
  12. 	a.Push(20);
  13.  
  14. 	a.ShowHeap();
  15. 	cout << endl;
  16.  
  17. 	a.Push(30);
  18.  
  19. 	a.ShowHeap(); 
  20. 	cout << endl;
  21.  
  22. 	a.Push(15);
  23.  
  24. 	a.ShowHeap();
  25. 	cout << endl;
  26.  
  27. 	a.Push(10);
  28.  
  29. 	a.ShowHeap();
  30. 	cout << endl;
  31.  
  32. 	a.Push(9);
  33.  
  34. 	a.ShowHeap();
  35. 	cout << endl;
  36.  
  37. 	a.Push(8);
  38.  
  39. 	a.ShowHeap();
  40. 	cout << endl;
  41.  
  42. 	a.Push(12);
  43.  
  44. 	a.ShowHeap();
  45. 	cout << endl;
  46.  
  47.  
  48. 	/*************删除***********/
  49. 	cout << "**********删除************" << endl;
  50. 	cout << a.Top() << endl;
  51. 	a.Pop();
  52. 	a.ShowHeap();
  53. 	cout << endl;
  54.  
  55. 	cout << a.Top() << endl;
  56. 	a.Pop();
  57. 	a.ShowHeap();
  58. 	cout << endl;
  59.  
  60. 	cout << a.Top() << endl;
  61. 	a.Pop();
  62. 	a.ShowHeap();
  63. 	cout << endl;
  64.  
  65. 	cout << a.Top() << endl;
  66. 	a.Pop();
  67. 	a.ShowHeap();
  68. 	cout << endl;
  69.  
  70. 	cout << a.Top() << endl;
  71. 	a.Pop();
  72. 	a.ShowHeap();
  73. 	cout << endl;
  74. 	
  75. 	cout << a.Top() << endl;
  76. 	a.Pop();
  77. 	a.ShowHeap();
  78. 	cout << endl;
  79.  
  80. 	cout << a.Top() << endl;
  81. 	a.Pop();
  82. 	a.ShowHeap();
  83. 	cout << endl;
  84.  
  85. 	a.Pop();
  86.  
  87. 	system("pause");
  88. 	return 0;
  89. }

结果展示

 

总结

        大顶堆和小顶堆都是堆数据结构的变种，它们分别能够在 O(1) 时间内访问最大和最小元素。在 C++ 中，可以方便地使用 std::priority_queue 创建并操作这两种堆。无论是大顶堆还是小顶堆，插入元素和删除堆顶元素的时间复杂度都是 O(log n)，其中 n 为堆中的元素数量。

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

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

  

闽ICP备14008679号