目录

一、堆

1、堆的概念

2、堆的性质

3、堆的分类

二、堆的向下调整算法

三、堆的创建 

四、堆的向上调整算法

五、堆的实现

1、堆的初始化

2、堆的销毁

3、堆的插入

4、堆的删除

5、获取堆顶的数据

6、堆的数据个数

7、堆的判空

8、堆的打印

9、测试小例子

 六、Topk问题

测试topk

一、堆

1、堆的概念

堆：如果有一个关键码的集合K={k0,k1,k2,…,kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足ki<=k2i+1且ki<=k2i+2（或满足ki>=k2i+1且ki>=k2i+2），其中i=0,1,2,…，则称该集合为堆。

2、堆的性质

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

②堆总是一棵完全二叉树。

3、堆的分类

大堆：将根节点最大的堆叫做最大堆或大根堆，父亲节点的值总是大于孩子。

小堆：根节点最小的堆叫做最小堆或小根堆，父亲节点的值总是小于孩子。

二、堆的向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

向下调整算法基本思想： （以建成小堆为例）

①从根节点开始，选出左右孩子节点中值较小的一个

②让父亲与较小的孩子比较

若父亲大于此孩子，那么交换

若父亲小于此孩子，则不交换

③结束条件

1、父亲<=小的孩子则停止

2、调整到叶子节点，（叶子节点特征为没有左孩子，就是数组下标超出了范围，就不存在了）

代码如下：

void Swap(int* x,int* y)
{
int*tmp=*x;
*x=*y;
*y=tmp;
}
void AdjustDown(int* a, int n, int parent) //注意右孩子可能不存在
{
	//child记录左右孩子中值较小的孩子的下标
	int child = 2 * parent + 1; //先默认其左孩子的值较小
	while(child<n)
	{ 
		if (child + 1 < n && a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
		{
			child++;//较小的孩子改为右孩子
		}
		if (a[child < a[parent]])
		{
			Swap(&a[child], & a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

详细的向下调整算法过程： 

三、堆的创建 

如何将一个任意树调整为堆呢？

这里我们可以利用刚刚写的堆的向下调整算法，我们知道，满足堆，必须左右子树都是大堆或者小堆，我们可以利用这个思想，从下往上倒着走，从第一个非叶子节点开始，通过数组下标的控制，把它当做根去向下调整，依次往上，直到把当前路径调整成符合条件的大堆或者小堆即可

代码如下：

	//建堆   n为数组个数  n-1为最后一个元素下标 （n-1-1）/2找到第一个非叶子节点的父亲
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(hp->a, hp->size, i);
	}

建堆的时间复杂度为O(N)

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

四、堆的向上调整算法

当我们已经有一个堆，我们需要在堆的末尾插入数据，再对其进行调整，使其任然保持堆的结构，这里我们就需要用到堆的向上调整算法

堆的向上调整算法基本思想：（以建小堆为例）

①将要插入的数据与其父节点数据比较

②若子节点数据小于父节点数据，则交换

若子节点数据大于父节点数据，则不交换，不需要调整，已经满足堆的结构

代码如下：

void Swap(int* x, int* y)
{
	int* tmp = *x;
	*x = *y;
	*y = tmp;
}
void AdjustUp(int * a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[child],&a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else 
		{
			break;
		}
	}
}

详细的向上调整算法：

 我们现在已经知道堆的向上和向下调整算法了，那么我们可以开始实现堆的结构了

五、堆的实现

我们需要一个结构体来表示堆

typedef int HPDataType;//方便后续修改数据类型
typedef struct Heap
{
	HPDataType* a;//用于动态开辟的指针
	int size;
	int capacity;
}Heap;

1、堆的初始化

我们依然将size和capacity置为0，数组a给为NULL。

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->capacity = hp->size = 0;
	hp->a = NULL;
}

2、堆的销毁

用于动态开辟的数组，为了避免内存泄漏我们都要将其释放，返还给操作系统

void HeapDestroy(Heap* hp)
{
	assert(hp);

	free(hp->a);//释放动态开辟的数组
	hp->a = NULL;//及时置空
	hp->capacity =hp->size = 0;//元素个数置0
}

3、堆的插入

我们要求堆插入数据后，其结构任然为堆，所以我们要对其进行向上调整，刚刚开始size和capacity都是0，所以我们要先进行扩容，再将数据放进去

void HeapPush(Heap* hp,HPDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		size_t newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
				exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

4、堆的删除

删除堆就是删除堆顶的数据，将堆顶的数据与最后一个数据交换，然后删除最后一个数据，剩下的数据在进行向下调整算法即可，由于数组结构，我们只需要size--就相当于删除了那个数据

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0],&hp->a[hp->size-1]);
	hp->size--;
	AdjustDown(hp->a,hp->size,0);
}

5、获取堆顶的数据

我们可以直接利用数组下标，返回数据即可

//取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}

6、堆的数据个数

直接返回size即可

//堆的总数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

7、堆的判空

判断堆中数据个数是否为0

//堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;//0为假   非0为真
}

8、堆的打印

void HeapPrint(Heap* hp)
{
	assert(hp);
	for(int i = 0; i < hp->size; i++)
	{
		printf("%d ",hp->a[i]);
	}
	printf("\n");
}

9、测试小例子

#include"Heap.h"

int main()
{
	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
	Heap hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		HeapPush(&hp, arr[i]);
	}
	HeapPrint1(&hp);
	HeapPop(&hp);
	HeapPop(&hp);
	HeapPop(&hp);
	HeapPop(&hp);
    HeapPrint1(&hp);
	printf("top=%d\n", HeapTop(&hp));
	printf("size=%d\n",HeapSize(&hp));
	HeapDestroy(&hp);
	return 0;

}

测试结果

 六、Topk问题

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

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

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

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

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

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

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

将剩余N-K个元素依次与堆顶元素比完之后

3.堆中剩余的K个元素就是所求的前K个最小或者最大的元素

代码如下： 

//topk问题
void PrintTopK(int* a, int n, int k) 
{
	// 1. 建堆--用a中前k个元素建堆(依次一个一个插入)
	Heap hp;
	HeapInit(&hp);
	for(int i=0;i<k;i++)
	{
		HeapPush(&hp,a[i]);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp,a[i]);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&hp);

	
}

测试topk

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand((unsigned int)time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}
int main()
{
	TestTopk();
	return 0;
}

这里我们利用随机数生成的方法，先随机生成了1万个小于10万的数字，然后再随机构造了10个大于10万的数字，我们利用Topk函数可以将这10个大于10万的数字给找出来！

测试结果：

 谢谢大家观看！