【数据结构】堆的实现（向上、下调整比较，复杂度，堆排序，Top-K问题）

文章目录

• 一、堆的实现
• • • 1、堆的概念
    • 2、堆的性质
    • 3、堆的实现
• 二、堆的创建（向上、下调整比较）
• 三、堆排序
• 四、Top-K（读取文件当中的数据）

一、堆的实现

1、堆的概念

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

2、堆的性质

1️⃣堆中某个节点的值总是不大于或不小于其父节点的值；
2️⃣堆总是一棵完全二叉树。

3、堆的实现

在这里主要是将代码展现在这里，算法实现将会在后面详细实现。
代码中包括初始化、打印、插入数据、删除数据、判断空、销毁堆、输出最大值最小值。

//初始化
void HpInit(Hp* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}
1
2
3
4
5
6
7

//插入数据
void HpPush(Hp* php, HPDataType x)
{
	assert(php);
	//判断是否需要扩容
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		//这里使用三目操作符更便捷，
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		//动态开辟空间
		if (tmp == NULL)
		{
			perror("malloc");
			exit(-1);
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
	//向上调整
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//向上调整
void AdjustUp(HPDataType* a, int child)
{
	//int child = n;
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//交换数据
void swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = * b;
	*b = temp;
}
1
2
3
4
5
6
7

//删除数据
void HpPop(Hp* php)
{
	assert(php);
	assert(!HpEmpty(php));
	swap(&php->a[0], &php->a[php->size-1]);
	//将最后一个元素和第一个元素进行交换
	php->size--;
	AdjustDown(php->a,php->size,0);
	//向下调整
}
1
2
3
4
5
6
7
8
9
10
11

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child<n)
	{
		if (child + 1 < n &&a[child] > a[child + 1])//建大小堆这里也是需要改的，现在是建小堆
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//销毁堆
void HpDestroy(Hp* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
//打印数据
void HpPrint(Hp* php)
{
	assert(php);
	for (int i = 0; i < php->size; ++i)
	{
		printf("%d ",php->a[i]);
	}
	printf("\n");
}
//判断是否为空
bool HpEmpty(Hp* php)
{
	assert(php);
	return php->size == 0;
}
//返回数据个数
int HpSize(Hp* php)
{
	assert(php);
	return php->size;
}
//返回堆顶数据
HPDataType HpTop(Hp* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

//将数组进行建堆                                                 
void HpCreat(Hp* php, HPDataType* a, int n)
{
	assert(php);
	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	php->a = tmp;
	memcpy( php->a,a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(php->a, n, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在这里就要讨论一个问题了，将数组变成堆为什么用向下调整，为什么不用向上调整？
下面就将具体的介绍一下为什么用向下调整，并且说明堆是如何创建的。

二、堆的创建（向上、下调整比较）

这个标题主要是讲堆的创建包括原理，向上、下调整比较，复杂度等问题。
我们知道堆在内存当中是以数组的形式来储存的，逻辑结构是完全二叉树。
实现原理：

代码实现如下：
下面所调用的函数在上面的有实现的代码。

//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(php->a, n, i);
	}
	//向上调整建堆
	for (int i = 1; i <n; i++)
	{
		AdjustUp(php->a,i);
	}
1
2
3
4
5
6
7
8
9
10

接下来证明一下为什么向下调整比向上调整要好！！！

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

向上调整证明：时间复杂度为O(NlogN)

它们的区别:因为树的结构是逐层递增的，向下调整开始的节点少调整的次数多，到后面节点多调整少。
而向上调整开始的时候节点少调整的也少，到后面节点多调整的也多，它们之间的差距就在这里。
当节点数N=1000时，向上调整要10000次，而向下调整要1000次他们之间的差距还是很大的，这也就是选择向下调整的原因。

三、堆排序

在之前建完堆之后我们可以看到并不是有序数组，所以就需要堆排序了。
堆排序原理：例如实现升序数组，在建完大堆之后，将堆顶的数据和最后一个数据进行交换，然后在堆顶进行向下调整（并不包括下面进行交换位置的数据）所以每次堆顶向下调整都会少一个数据。就这样最大的数据，次大的数据就一个一个的交换在下面了。
并不需要开辟新的空间空间复杂度：O(1)
时间复杂度：O(N*logN)
N(建堆) + N* logN(排序) = N*logN 将N省略了

//堆排序
void HpSort(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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、Top-K（读取文件当中的数据）

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

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

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

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

• 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

下面我们来对比一下上面的方法和在之前堆中实现的一个一个的Pop哪更快
K为需要找出K个数据，N为数据总个数
上面方法：K(建堆) + （N-k）logK(剩下的数据进行的比较和调整，复杂度取最坏结果)
时间复杂度：O(NlogK)
空间复杂度：O(k)
使用Pop方法：N(建堆) + KlogN
时间复杂度：O(N+K*logN)
空间复杂度：O(1)
实现代码如下：
使用rand函数创造一些随机数据存放在文件中，在文件中找TopK。

void HeapTest4()
{
	int k, n;
	printf("请输入取TOP的数量和总数据的大小:");
	scanf("%d%d",&k,&n);
	srand(time(0));
	FILE* pf = fopen("test.txt","w");
	if (pf == NULL)
	{
		perror("fopen");
		exit(-1);
	}
	for (int i = 0; i < n; i++)
	{
		int sat = rand() % 10000;
		//创造随机数
		fprintf(pf,"%d\n",sat);
	}
	fclose(pf);
	pf = NULL;
	FILE* ppf = fopen("test.txt", "r");
	if (ppf == NULL)
	{
		perror("fopen");
		exit(-1);
	}
	int* tmp = (int*)malloc(sizeof(int)*k);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	int j = 0;
	for (; j < k;++j)
	{
		fscanf(ppf,"%d",&tmp[j]);
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(tmp, k, i);
		//建堆（向下调整）
	}

	int val = 0;
	while (fscanf(ppf, "%d", &val) != EOF)
	{
		if (val > tmp[0])
		{
			tmp[0] = val;
			AdjustDown(tmp, k, 0);
			//将剩下的数据进行比较，以及调整。
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ",tmp[i]);
	}

	fclose(ppf);
	ppf = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

输出结果如下：