【C语言】什么是堆？堆排序和TopK问题又是如何实现的
慕雪年华
  2022-04-11 16:29:28 2022-04-11 16:29   2023-04-03 09:23:39    3.9k 字  

[TOC]

前言

在上一篇数据结构博客中，我带大家一起学习了树以及二叉树这一个全新的数据结构。

【C语言】什么是树，二叉树又是啥玩意

本篇博客，就让我们一起来看看常被人津津乐道的堆排序以及堆这个数据结构是一个什么样的存在吧？

1.堆的概念

堆的概念是基于完全二叉树的

当k1、k2、k3……kn的数据按照完全二叉树的方式存放在数组中，且这个完全二叉树满足某个节点的值总是不大于（或不小于）其父节点的值时，称该完全二叉树为堆。

  • 将根节点最大的堆叫大根堆
  • 根节点最小的堆叫做小根堆
  • 堆中某个节点的值总是不大于（或不小于）其父节点的值

上篇树的博客中已经给大家解释过如何用数组的方式存放一颗完全二叉树，这里就不再赘述啦！

1
2
3
leftchild=parent*2+1
rightchild=parent*2+2
parent=(child-1)/2

接下来这道题目能考察你是否了解了堆的概念，自测一下吧！

1
2
3
4
5
2.下列关键字序列中，序列（ ）是堆。
A .{16，72，31，23，94，53}
B .{94，23，31，72，16，53}
C .{16，53，23，94，31，72}
D .{16，23，53，31，94，72}   √

简单说来，以0下标根为例，下标1和2为根的左右孩子。如果他们都比根小，代表这是一个小根堆，反之是大根堆。

接着我们就需要判断，是不是所有节点的孩子都满足这个特性，如果出现某一个节点的孩子和该节点的父亲之间的关系不满足根节点和孩子之间的关系（如根节点的孩子比根节点大，那么该树中所有节点的孩子都应该比该节点大）那么这个就不是一个堆

2.堆的实现

先来尝试直接实现一个堆，即将数据以堆的结构存放在数组中

这里给出一个堆的头文件，里面包含了一个堆的基本框架

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
//实现一个小堆
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;

void HeapInit(HP* php);//初始化-不进行扩容操作
void HeapDestroy(HP* php);//摧毁
void HeapPrint(HP* php);//打印

//交换数组中两个元素的位置
void Swap(HPDataType* pa, HPDataType* pb);

//插入后向上调整，保证数据是(大/小)堆
//child为待操作数据的下标
void AdjustUp(HPDataType* a, size_t child);
// 插入x以后，保持他依旧是(大/小)堆
void HeapPush(HP* php, HPDataType x);


//删除后向下调整，保证数组末尾数据位置正确
//size堆的大小；root待调节数据的位置，0代表根部（堆顶）
void AdjustDown(HPDataType* a, size_t size, size_t root);
// 删除堆顶的数据。(最小/最大)；
// 交换堆顶数据和数组末尾数据
void HeapPop(HP* php);

//判断是否为空
bool HeapEmpty(HP* php);
//返回堆的大小（节点个数）
size_t HeapSize(HP* php);
//返回堆顶，访问数组下标0
HPDataType HeapTop(HP* php);

2.1向上调整

你会发现，相较于普通数据结构的增加、删除操作，堆有一个额外的操作，就是调整数据的位置。

本篇博客不再对前面的基础操作进行讲解，如果有不会的可以评论区提出哦

比如下面这幅图里的数组，我们可以直接在数组的末尾插入一个数据6，因为当前的这个堆是一个小堆，堆顶的数据是最小的数据，所以我们不需要对这个数据进行处理

image-20220411144114070

但当我们插入一个0，事情就不一样了。我们必须将这个0调整到堆顶的位置，才能让插入数据后的数组依旧是一个小堆

image-20220411144729371

转换为树的形状，即为下图

image-20220411144720588

我们需要让在叶节点的0往上爬，来到1的位置

如何操作呢？

将该节点与它的父节点进行比较，如果父节点大于该节点，则交换两个节点的位置。

通过循环的来完成一个完整的向上调节工作

在上篇博客中，我提到了下图所示的计算公式。使用这个公式来进行父节点和孩子节点的查找工作，再单独编写一个Swap函数进行交换

image

代码实现如下

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
//交换数组中两个元素的位置
void Swap(HPDataType* pa, HPDataType* pb) 
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//向上调整，保证数据是(大/小)堆
//child为待调整数据的下标位置
void AdjustUp(HPDataType* a, size_t child)
{
	assert(a);//这里依旧需要断言，因为用户可能单独调用这个函数

	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] < a[parent])//小堆，小的数据往上调
		{
			Swap(&a[child], &a[parent]);
			child = parent;
		}
		else
		{
			return;
		}
	}
}

// 插入x以后，保持他依旧是(大/小)堆
// O(logN)
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		//如果容量为0，新容量为4；不为0，新容量为原本容量的2倍
		int newcapa = php->capacity==0 ? 4: php->capacity*2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapa*sizeof(HPDataType));//realloc接收空指针，作用与malloc相同
		if (tmp == NULL)
		{
			printf("realloc failed!\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapa;
	}

	php->a[php->size] = x;//在数组末尾插入新数据
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

下图更加清晰地展示了向上调整函数的作用过程

image-20220411145413246

2.2向下调整

同理，当我们pop掉一个堆顶的数据之后，就需要进行一定的调整，来维持堆的结构

这里需要注意一个问题，栈顶的数据并不能直接pop掉，因为会破坏掉堆的结构。

比如下面的这个堆中，如果我们直接删除掉堆顶的元素1，那请问谁来当新的爸爸呢？

image-20220411145648411

为了方便这里数据的处理，我们要先将堆顶的元素和数组的最后一个元素进行交换，再进行pop操作。

image-20220411145910611

因为我们的堆是用顺序表实现的，所以交换后，只需让size--即可达到pop的效果

那么如何让8往下掉呢？

同样是利用上面提到过的关系公式👉点我回到之前的公式图

我们需要将8和它的孩子进行比较，如果8大于它的孩子，则进行交换。

代码实现如下👇

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
//删除后向下调整，保证数组末尾数据位置正确
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	assert(a);
	int parent = root;
	int child = parent * 2 + 1;//左孩子
	while (child < size)
	{
		
		//找左右孩子中小的那一个
		if (child + 1 < size && a[child] > a[child + 1])
		{//如果左孩子大于右孩子，则选择右孩子
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			return;
		}
	}

}
// 删除堆顶的数据。(最小/最大)；
// 交换堆顶数据和数组末尾数据
void HeapPop(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.3代码测试

老样子，一定要写完一个模块后，立马测试一个模块！

image-20220411150703039

3.堆排序

上面我们自己实现了一个堆的代码，接下来我们可以借助这个堆的代码，进行排序操作。（解析见代码注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void HeapSort(int* a, int size)
{
	// 小堆-升序
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);//往堆内放入数据
	}

	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);//每一次都堆顶数据出来放入数组
		j++;
		HeapPop(&hp);//删除堆顶数据，重新排序
	}

	HeapDestroy(&hp);
}

可以看到，上述代码成功排序

image-20220411151609772

3.1为什么要进行堆排序？

看到这里，你可能会有一个疑惑：排序的方式有很多种，我们可以直接冒泡排序，也可以利用库函数qsort进行排序，为什么要采取堆排序这种方式呢？还需要写一个堆的代码，多麻烦啊！

QQ图片20220411151827

要想解答这个问题，我们先来看看冒泡排序算法和堆排序算法的时间复杂度

  • 冒泡排序：遍历一遍数组是N，调整一次数据也是N，时间复杂读是O(N^2^)
  • 堆排序：建堆是O(N*logN)，取堆顶数据是O(N)，时间复杂度是O(N*logN)

如果你不了解什么是时间复杂度，可以看看我的这篇博客👉传送门

对于我示例中这个10个元素的数组来说，这两个时间复杂度的差距可能不是很大，但对于海量数据来说，差距就起飞啦！

数据个数O(N*logN)O(N^2^)
10001000×101000×1000
100w100w×20100w×100w

这个数据的差距可大的很呢！😱

从上面的解释，你应该能看出来，堆排序是挺优秀！

但是我们一般并不会写上面的代码，因为它需要另建一个堆来存放数据，空间复杂度是O(N)

有没有什么办法，能够在原本的数组上建堆，来进行排序呢？

3.2在原本数组上建堆

直入主题，我们可以直接在原本的数据上，利用堆的向上/下调整算法，建立一个大堆或者小堆来进行排序。

3.2.1向上调整-插入数据

使用插入数据的思想，我们可以把数组第二个元素当作新的元素进行push操作，并利用向上调整算法来调整它们的位置，以此类推，这样就能建成一个堆。

但是这个方法对于升序来说不够优化，后续会提到具体原因

3.2.2 向下调整-删除数据

假设我们有一个这样的数组（它现在还不算一个堆）

image-20220411154000249

我们可以从第一个非叶子节点（即8）开始，进行向下调整，如果它的孩子比它小，则进行交换。处理完8后，进一步处理7、2、4……

最终我们会得到这样的一个小堆

image-20220411154337119

此时再将第一个数据和末尾数据进行交换，pop掉它，让它成为数组尾部的数据。再进行向下调整操作，依次循环，即可完成一个降序的排列

3.2.3比较时间复杂度

我们来比较一下上面两个方法的时间复杂度。

image-20220411154622739

如果是向上调整的话，第二层的2个节点要向上调整1次，第三层的4个节点要向上调整2次，最后累积，我们会得到下面这个公式
$$
T(h)=2^11+2^22+2^33+……+2^{h-1}(h-1)
$$
数学好的你，估计一眼就能看出来，这是一个等差×等比形式的数列，可以利用

  • 错位相减法，高考第17题，如果出上面这个式子，属于送分题
  • 快一年过去了，现在的我看到这个式子，属于送命题

好吧其实也没那么难😂

image-20220411160107459

如果是向下调整算法，第一层要向下移动h-1层，第二层要向下移动h-2层，第h-1层需要往下移动1层，我们能得到下面的公式

最后能得出，需要移动的总步数为

在N很大的时候，减去的log(n+1)可以忽略，时间复杂度为O(N)

由此可见，向下调整算法是更优的，它的时间复杂度更小

3.3代码示例

弄明白思路后，写代码就很简单啦！

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
// 升序用大堆
// 降序用小堆
void HeapSort(int* a, int n)
{
	// 向上调整--建堆 O(N*logN)
	//for (int i = 1; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}

	// 向下调整--建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);//此时建的是一个小堆
	}

	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
        //前后交换，最小的数组放到末尾，不进行下一次调整
		AdjustDown(a, end, 0);
		end--;
	}
	//现在是小堆代码，所以排序出来是降序
}

测试一下代码，完美排序出了降序

image-20220411160857078

如果你需要升序的话，只需将原本实现的小堆代码中的判断条件改一下就行了

image-20220411161051910

4.TopK问题

4.1问题说明

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

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

对于Top-K问题，能想到的最简单直接的方式就是排序。有两个思路

  • 堆排序：时间复杂度O(N*logN)，空间复杂度O(1)
  • 在原本的数组上建立N个数的大堆，Pop K次，就能选出最大的前K个。时间复杂度O(N+K*logN)，空间复杂度：O(1)

但是，如果数据量非常大，上面这两个方法就不太可取了(可能数据都不能一下子全部加载到内存中，而是存放在硬盘里面)

image-20220411161351578

4.2如何求解？

用前K个数建立一个K个数的小堆，然后剩下的N-K个数依次遍历，如果比堆顶的数据大，就替换它进堆（进堆后要进行向下调整），最后堆里面的K个数据就是最大的前K个

代码示例如下

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
void PrintTopK(int* a, int n, int k)
{
	// 1.建堆--用a中前k个元素建堆
	int* kminHeap = (int*)malloc(sizeof(int) * k);
	assert(kminHeap);

	for (int i = 0; i < k; ++i)
	{
		kminHeap[i] = a[i];
	}

	//利用小堆代码的向下调整，建一个小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(kminHeap, k, j);
	}
	//堆顶是这个堆里面最小的数据
	//2.将剩余n-k个元素依次与堆顶元素判断，如果大于堆顶，则交换
	for (int i = k; i < n; ++i)
	{
		if (a[i] > kminHeap[0])
		{
			kminHeap[0] = a[i];
			AdjustDown(kminHeap, k, 0);
		}
	}

	for (int j = 0; j < k; ++j)
	{
		printf("%d ", kminHeap[j]);
	}
	printf("\n");
	free(kminHeap);
}
  • 时间复杂度：O(K+logK*(N-K))
  • 空间复杂度：O(K)

当N非常大，K很小的时候，这个算法的时间复杂度基本就是O(N)

4.3测试代码

通过time函数和srand函数，我们可以将一个10000个数的数组中的每个元素赋值小于100w的随机数，再在随机位置放入10个大于100w的数字。

可以看到，上面的代码巧妙利用堆的知识，帮我们找出了这个10000个数的数组中最大的前K个数字

image-20220411162041637

结语

堆和堆排序的知识到这里就讲解完毕啦！如果你还有什么问题，可以在评论区留言哦~

QQ图片20220411162629

如果对你有帮助，还请点个👍，万分感谢！

  • 本文标题：【C语言】什么是堆？堆排序和TopK问题又是如何实现的
  • 本文作者：慕雪年华
  • 创建时间：2022-04-11 16:29:28
  • 本文链接：posts/3640362579/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  1. 前言
  2. 1.堆的概念
  3. 2.堆的实现
    1. 2.1向上调整
    2. 2.2向下调整
    3. 2.3代码测试
  4. 3.堆排序
    1. 3.1为什么要进行堆排序？
    2. 3.2在原本数组上建堆
      1. 3.2.1向上调整-插入数据
      2. 3.2.2 向下调整-删除数据
      3. 3.2.3比较时间复杂度
    3. 3.3代码示例
  5. 4.TopK问题
    1. 4.1问题说明
    2. 4.2如何求解？
    3. 4.3测试代码
  6. 结语