数据结构——堆

前言

一、堆的概念及结构

二、堆的实现

2.1 堆初始化

前言

之前我们了解到了一种非线性的数据结构——树，今天我们来学习二叉树的顺序结构——堆的实现，来了解堆这种数据结构。

一、堆的概念及结构

如果有一个关键码的集合K = { ，，，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <=且 <=( >=且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

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

堆总是一棵 完全二叉树 。

二、堆的实现

在物理结构上我们通过一个一维数组来实现堆，逻辑上堆为完全二叉树。

堆的结构：


typedef int HPDataType;
 
typedef struct Heap {
	HPDataType* a;
	int size;//有效数据个数
	int capacity;//数组大小
}HP;

主要接口：


//堆初始化
void HPInit(HP* php);
//堆的插入(插入后保持为堆)
void HPPush(HP* php, HPDataType x);
//向上调整
AdjustUp(HPDataType* a, int chlid);
//堆的删除(删除堆顶元素)
void HPPop(HP* php);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//取堆顶
HPDataType HPTop(HP* php);
//判空
bool HPEmpty(HP* php);
//堆的销毁
void HPDestroy(HP* php);
 
//交换数据
void Swap(HPDataType* p1, HPDataType* p2);

2.1 堆初始化


void HPInit(HP* php) {
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
 
}

和之前顺序表的初始化一样，把数组置空，大小和容量都为空。

2.2 堆的销毁


void HPDestroy(HP* php) {
	assert(php);
 
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
 
}

释放我们开辟的数组空间，其他都置为空。

2.3 交换数据


void Swap(HPDataType* p1, HPDataType* p2) {
	HPDataType temp = 0;
	temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

定义一个交换函数，后面操作会用到。

2.4 插入数据(插入到堆尾)

插入数据后，我们还要插入后保持结构为堆。


void HPPush(HP* php, HPDataType x) {
	assert(php);
 
	//扩容
	if (php->size == php->capacity)
	{
		int Newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->a, Newcapacity * sizeof(HPDataType));
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}
 
		php->a = temp;
		php->capacity = Newcapacity;
	}
	php->a[php->size++] = x;
 
	//向上调整
	AdjustUp(php->a, php->size-1);
}

前面的插入操作和顺序表都插入一样，我们插入到堆的最后面，同时我们需要一个向上调整函数来保持结构仍为堆。

2.5 向上调整

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆


AdjustUp(HPDataType* a, int chlid) {
	//父节点
	int parent = (chlid - 1) / 2;
 
	//先上调整
 
	while (chlid > 0)
	{
		if (a[chlid] < a[parent])
		{
			Swap(&a[parent], &a[chlid]);
			//新的父子节点
			chlid = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
 
}

我们从子节点找它的父节点，比较父子节点的大小，如果堆为小堆，则谁更小谁在上面，反之如果为大堆，则谁更大谁在上面。

2.6 堆的删除(删除堆顶元素)


void HPPop(HP* php) {
	assert(php);
	assert(php->size > 0);
	//把堆顶元素和最后一个元素交换位置
	Swap(&php->a[0],&php->a[php->size - 1]);
	php->size--;
 
	//向下调整
	AdjustDown(php->a,php->size,0);
}

堆的删除操作，我们先把堆顶元素和堆尾元素交换位置，最后堆的长度减一即可(可以不用删除)，最后通过向下调整来保持堆的结构。

2.7 向下调整

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。


void AdjustDown(HPDataType* a, int n, int parent) {
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
 
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
 
	}
}

我们通过父节点来找到子节点，我们首先找到左右节点中最小的(反之如果是大堆找最大的)，找到后比较子节点和父节点中最小的交换位置(反之如果是大堆找最大的)。

2.8 取堆顶


//取堆顶
HPDataType HPTop(HP* php) {
	assert(php);
	
	return php->a[0];
}

因为堆是通过数组实现的，所以堆顶即为数组第一个元素。

2.9 判空


bool HPEmpty(HP* php) {
	assert(php);
	return php->size == 0;
}

测试代码：


#include"Heap.h"
 
int main() {
	HP hp;
	HPInit(&hp);//初始化堆
	int a[] = { 50,100,70,65,60,32 };
	for(int i = 0; i < sizeof(a) / sizeof(a[0]);i++)
	{
        //把数组的内容依次插入到堆中
		HPPush(&hp, a[i]);
	}
	while (!HPEmpty(&hp))
	{    
		printf("%d\n", HPTop(&hp));
		HPPop(&hp);
	}
 
 
	HPDestroy(&hp);
}

完整代码


//堆初始化
void HPInit(HP* php) {
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
 
}
 
//交换数据
void Swap(HPDataType* p1, HPDataType* p2) {
	HPDataType temp = 0;
	temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
 
//向上调整
AdjustUp(HPDataType* a, int chlid) {
	//父节点
	int parent = (chlid - 1) / 2;
 
	//先上调整
 
	while (chlid > 0)
	{
		if (a[chlid] < a[parent])
		{
			Swap(&a[parent], &a[chlid]);
			//新的父子节点
			chlid = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
 
}
 
//堆的插入(插入后保持为堆)
void HPPush(HP* php, HPDataType x) {
	assert(php);
 
	//扩容
	if (php->size == php->capacity)
	{
		int Newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->a, Newcapacity * sizeof(HPDataType));
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}
 
		php->a = temp;
		php->capacity = Newcapacity;
	}
	php->a[php->size++] = x;
 
	//向上调整
	AdjustUp(php->a, php->size-1);
}
 
//向下调整
void AdjustDown(HPDataType* a, int n, int parent) {
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
 
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
 
	}
}
 
//堆的删除(删除堆顶元素)
void HPPop(HP* php) {
	assert(php);
	assert(php->size > 0);
	//把堆顶元素和最后一个元素交换位置
	Swap(&php->a[0],&php->a[php->size - 1]);
	php->size--;
 
	//向下调整
	AdjustDown(php->a,php->size,0);
}
//取堆顶
HPDataType HPTop(HP* php) {
	assert(php);
	
	return php->a[0];
}
//判空
bool HPEmpty(HP* php) {
	assert(php);
	return php->size == 0;
}
//堆的销毁
void HPDestroy(HP* php) {
	assert(php);
 
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
 
}

三、堆的创建

前面我们通过数组插入堆来建堆，我们还可以通过其他方法来创建堆


int main() {
	HP hp;
	int a[] = { 50,100,70,65,60,32 };
	HPInitArray(&hp,a,sizeof(a) / sizeof(a[0]));
}

1.向上调整建堆


void HPInitArray(HP* php, HPDataType* a, int n) {
	//为堆开辟空间
    php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	//拷贝数组的值到堆中
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
 
	//向上调整建堆  O(N*longN)
	for (int i = 1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}
}

我们从堆的第二个节点开始先上开始调整的。

向上调整建堆的时间复杂度为：O(N*longN)

2.向下调整建堆


void HPInitArray(HP* php, HPDataType* a, int n) {
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	//拷贝数组的值到堆中
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
 
	//向下调整建堆 O(N)
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
 
}

我们先下调整的初始位置为最后一个子节点的父节点开始向下调整的。

向下调整的时间复杂度为：O(N)

所以我们通常使用向下调整建堆，时间复杂度小。

四、堆的应用

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

4.1 堆排序

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。


#include"Heap.h"
 
void HeapSort(HPDataType* a, int n) {
 
	//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
	//小堆降序  大堆升序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0],&a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
 
}
 
int main() {
	int a[] = { 20,17,5,3,4,16 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	
}

升序：建大堆

降序：建小堆

4.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能

数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

我们先在文件中创建出数据：


void CreateNdate()
{
	int n = 1000;//个数
	srand(time(0));
 
	FILE* fin = fopen("date.txt", "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
 
	int x = 0;
	for (int i = 0; i < n; i++)
	{
		x = (rand() + i) % 10000000;
		fprintf(fin, "%d\n",x);
	}
	fclose(fin);
}

然后通过建堆比较来使得堆里元素为最大(或最小)


void tok() {
 
	int k = 0;
	printf("请输入k的值>");
	scanf("%d", &k);
	FILE* fout = fopen("date.txt", "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	int* minheap = (int*)malloc(sizeof(int) * k);
 
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
 
	//建一个k的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}
 
	int x = 0;
    //比较
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	fclose(fout);
}

比如我们求1000个数中前10个最大的：

总结

以上我们讲了二叉树的顺序结构——堆，讲了堆的实现，和堆的应用。希望对你有所帮助。

相关阅读:
servlet页面以及控制台输出中文乱码
 代码信息化:软件业“第二次工业革命”的契机
 前端框架的发展史&介绍框架特点
 88-Spring Boot详解
 Web前端大作业——基于HTML+CSS+JavaScript仿英雄联盟LOL游戏网站
 java-对Integer.MAX_VALUE做加法
 如何提高系统的可用性/高可用
 JVM八股文
 SAP PP cs62 提示输入更改号 - BOM 有历史需求
 软件工程毕业设计课题（71）微信小程序毕业设计PHP校园浴室预约小程序系统设计与实现
原文地址：https://blog.csdn.net/2301_76613753/article/details/138002661