目录

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.堆的算法实现

堆数据结构的定义： 

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

建立最大堆算法：  

bool initHeap(Heap& heap, int* original, int size);
static void buildHeap(Heap& heap);
static void adjustDown(Heap& heap, int index);

//初始化堆
bool initHeap(Heap& heap, int* original, int size) {
	//如果默认大小比size小，则申请默认大小的空间，否则申请size大小的空间
	int capacity = DEFAULT_CAPACITY > size ? DEFAULT_CAPACITY : size;
	heap.arr = new int[capacity];
	if (!heap.arr)return false;
	heap.capacity = capacity;
	heap.size = 0;
	//如果存在原始数据，则拷贝过来
	if (size > 0) {
		memcpy(heap.arr, original, size * sizeof(int));
		heap.size = size;
		buildHeap(heap);
	}
	return true;
}

/*从最后一个父节点开始（heap.size) - 1 / 2）（因为size是从1开始，所以要先减去1）
逐个调整所有的父节点（直到根节点），确保每一个父节点都是最大堆，最后
整体上形成一个最大堆*/
void buildHeap(Heap& heap) {
	for (int i = (heap.size - 1) / 2; i >= 0; i--) {
		adjustDown(heap, i);
	}
}

void adjustDown(Heap& heap, int index) {
	int cur = heap.arr[index];  //记录父节点值
	int parent, child;

	/*怕段是否存在大于当前结点的子节点，如果不存在，则堆本身平衡，不需要
	调整，如果存在，则将最大子节点与之交换，交换后，如果这个子节点还有
	子节点（即parent*2+1<heap.size 成立）则要按照相同步骤对这个子节点进行
	调整*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
		child = parent * 2 + 1; //左子节点

		//取两个子节点最大结点
		if (((child + 1) < heap.size) && (heap.arr[child + 1] > heap.arr[child])) {
			child++;
		}
		if (cur >= heap.arr[child])break;//不大于，跳出循环
		else {
			/*大于当前父节点，进行交换，然后从子节点位置继续向下调整，
			即for从第二次循环开始，初始值都为上一次的子节点位置*/
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}
	}
}

完成测试代码 ：

int main() {

	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };

	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}

	for (int i = 0; i < hp.size; i++) {
		cout << hp.arr[i] << endl;
	}
	system("pause");
	return 0;
}

运行结果：

知识点补充：

1.memcpy(内存拷贝函数)

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

double arryDouble_Src[16];
double arryDouble_Det[16];

memcpy( arryDouble_Det, arryDouble_Src, sizeof(double)*16);

int arryInt_Src[16];
int arryInt_Dst[16];

memcpy( arryInt_Dst, arryInt_Src, sizeof(int)*16);

struct DataNum
{
	int Data0;
	int Data1;
}

DataNum arryStruct_Src[16];
DataNum arryStruct_Dst[16];

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, 至此，最大堆调整完成。 

 代码实现：

static bool insertHeap(Heap& heap, int value);
static void adjustUp(Heap& heap, int index);

bool insertHeap(Heap& heap, int value) {
	if (heap.size == heap.capacity) {
		fprintf(stderr, "栈空间耗尽!\n");
		return false;
	}

	int index = heap.size;
	heap.arr[heap.size++] = value;//先赋值value，再size++
	adjustUp(heap, index);
}

void adjustUp(Heap& heap, int index) {
	if (index < 0 || index >= heap.size) {
		//如果只有一个结点（插入的结点）inedx<0，或者大于堆的最大值，return掉
		return;
	}
	int temp = heap.arr[index];//temp为插入的值
	while (index > 0) {
		
		int parent = (index - 1) / 2;
		if (parent >= 0) {   //如果索引没有出界，就执行想要操作
			if (heap.arr[parent] < temp) {
				heap.arr[index] = heap.arr[parent];
				heap.arr[parent] = temp;
				index = parent;
			}
			else break;    //如果没有比父结点大，则跳出
		}
		else break;  //越界，结束循环
	}
}

完成测试代码 ： 

int main() {

	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };

	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}

	for (int i = 0; i < hp.size; i++) {
		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
	}

	insertHeap(hp, 99);
	printf("在堆中插入新的元素99，插入结果：\n");
	for (int i = 0; i < hp.size; i++) {
		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
	}
	system("pause");
	return 0;
}

运行结果：

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

 4.2弹出最大元素  

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

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

static bool popMax(Heap& heap, int& value);
bool popMax(Heap& heap, int& value) {
	if (heap.size < 1)return false;
	value = heap.arr[0];

	//将size-1的位置值赋给根节点，size本身又--
	/*相当于
		heap.arr[0] = heap.arr[heap.size-1];
		heap.size--;
	*/
	heap.arr[0] = heap.arr[--heap.size];
	adjustDown(heap, 0);  //向下执行堆调整
	return true;
}

完成测试代码 ： 

int main() {

	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };

	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}

	for (int i = 0; i < hp.size; i++) {
		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
	}

	/*向堆中插入元素
	insertHeap(hp, 99);
	printf("在堆中插入新的元素99，插入结果：\n");
	for (int i = 0; i < hp.size; i++) {
		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
	}*/

	int value;
	while (popMax(hp, value)) {
		cout << "依次出列最大元素：" << value << endl;
	}	
	
	system("pause");
	return 0;
}

运行结果：   

 

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

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

5.1优先队列

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

 

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

5.2堆排序

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

核心排序如下：

 

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

#include<iostream>
using namespace std;

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


bool initHeap(Heap& heap, int* original, int size);
static void buildHeap(Heap& heap);
static void adjustDown(Heap& heap, int index);
static bool insertHeap(Heap& heap, int value);
static void adjustUp(Heap& heap, int index);
static bool popMax(Heap& heap, int& value);

//初始化堆
bool initHeap(Heap& heap, int* original, int size) {
	//如果默认大小比size小，则申请默认大小的空间，否则申请size大小的空间
	int capacity = DEFAULT_CAPACITY > size ? DEFAULT_CAPACITY : size;
	heap.arr = new int[capacity];
	if (!heap.arr)return false;
	heap.capacity = capacity;
	heap.size = 0;
	//如果存在原始数据，则拷贝过来
	if (size > 0) {
		memcpy(heap.arr, original, size * sizeof(int));
		heap.size = size;
		buildHeap(heap);
	}
	return true;
}

/*从最后一个父节点开始（heap.size) - 1 / 2）（因为size是从1开始，所以要先减去1）
逐个调整所有的父节点（直到根节点），确保每一个父节点都是最大堆，最后
整体上形成一个最大堆*/
void buildHeap(Heap& heap) {
	for (int i = (heap.size - 1) / 2; i >= 0; i--) {
		adjustDown(heap, i);
	}
}

void adjustDown(Heap& heap, int index) {
	int cur = heap.arr[index];  //记录父节点值
	int parent, child;

	/*怕段是否存在大于当前结点的子节点，如果不存在，则堆本身平衡，不需要
	调整，如果存在，则将最大子节点与之交换，交换后，如果这个子节点还有
	子节点（即parent*2+1<heap.size 成立）则要按照相同步骤对这个子节点进行
	调整*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
		child = parent * 2 + 1; //左子节点

		//取两个子节点最大结点
		if (((child + 1) < heap.size) && (heap.arr[child + 1] > heap.arr[child])) {
			child++;
		}
		if (cur >= heap.arr[child])break;//不大于，跳出循环
		else {
			/*大于当前父节点，进行交换，然后从子节点位置继续向下调整，
			即for从第二次循环开始，初始值都为上一次的子节点位置*/
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}
	}
}
static bool popMax(Heap& heap, int& value);
bool popMax(Heap& heap, int& value) {
	if (heap.size < 1)return false;
	value = heap.arr[0];

	//将size-1的位置值赋给根节点，size本身又--
	/*相当于
		heap.arr[0] = heap.arr[heap.size-1];
		heap.size--;
	*/
	heap.arr[0] = heap.arr[--heap.size];
	adjustDown(heap, 0);  //向下执行堆调整
	return true;
}


bool insertHeap(Heap& heap, int value) {
	if (heap.size == heap.capacity) {
		fprintf(stderr, "栈空间耗尽!\n");
		return false;
	}

	int index = heap.size;
	heap.arr[heap.size++] = value;//先赋值value，再size++
	adjustUp(heap, index);
}

void adjustUp(Heap& heap, int index) {
	if (index < 0 || index >= heap.size) {
		//如果只有一个结点（插入的结点）inedx<0，或者大于堆的最大值，return掉
		return;
	}
	int temp = heap.arr[index];//temp为插入的值
	while (index > 0) {
		
		int parent = (index - 1) / 2;
		if (parent >= 0) {   //如果索引没有出界，就执行想要操作
			if (heap.arr[parent] < temp) {
				heap.arr[index] = heap.arr[parent];
				heap.arr[parent] = temp;
				index = parent;
			}
			else break;    //如果没有比父结点大，则跳出
		}
		else break;  //越界，结束循环
	}
}



int main() {

	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };

	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}

	for (int i = 0; i < hp.size; i++) {
		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
	}

	//向堆中插入元素
	insertHeap(hp, 99);
	printf("在堆中插入新的元素99，插入结果：\n");
	for (int i = 0; i < hp.size; i++) {
		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
	}

	int value;
	while (popMax(hp, value)) {
		cout << "依次出列最大元素：" << value << endl;
	}	
	
	system("pause");
	return 0;
}

运行截图：

# c++ # 数据结构 # 开发语言
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

OpenLoong项目通过技术监督委员会（TOC）评审

OpenLoong项目通过技术监督委员会（TOC）评审

avatar 开放原子开发者工作坊

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

avatar 开放原子开发者工作坊

开发者谈开源：洞悉协作创新背后的机遇与挑战

近日，在2024开放原子开发者大会暨首届开源技术学术大会开幕式上，开放原子开源基金会与openKylin、EasyAda、KWDB开源项目举行捐赠签约仪式。 一场捐赠签约仪式，让三个开源项目及其背后的开发者们受到瞩目。本次，我们与“龘”（EasyAda）核心维护者王伶卓开启了对话。

avatar 开放原子开发者工作坊