堆的应用：堆排序及TopK问题

---

前言

前一篇文章介绍了堆的概念及结构和堆的实现，堆的物理结构是数组实现的，但是要把它的逻辑结构想象成完全二叉树，并且了解到堆的增删数据后还要保持其原来的结构，因此需要采用向上和向下调整算法，最多调整该二叉树的高度(logN )次。
堆的的本质是方便找出次大或者次小的数，因此本文来介绍第一次接触到的时间复杂度为O(N*logN)的排序：堆排，以及利用堆排思想来解决TopK问题。

---

1. 堆排序

给你一个数组，如何建堆？如果直接实现堆的话，再把数组的数据依次插入堆的话，那么它的空间复杂度就是O(N)，是否可以直接操作原数组建堆呢？

1.1 向下还是向上调整

依旧采用小堆

最容易想到的方法就是模拟插入堆，然后依次向上调整。

从数组的第二个元素开始模拟插入堆，因为第一个数据就直接可以看成堆，然后向上调整建堆(模拟插入堆的过程)：

1.1.1 向上调整建堆

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
//1. 向上调整
void AdjustUp(int* heap, int child)
{
	int father = (child - 1) / 2;
	while (child > 0 && heap[father] > heap[child])
	{
		Swap(&heap[father], &heap[child]);
		child = father;
		father = (child - 1) / 2;
	}
}

void HeapSort(int* heap, int heapSize)
{
	for (int i = 1; i < arrSize; ++i)
	{
		AdjustUp(arr, i);
	}
	//...排序 
}
int main()
{
	int arr[] = { 65,100,70,32,60,50 };
	int arrSize = sizeof(arr) / 4;
	HeapSort(arr, arrSize);
	return 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

1.1.2 向下调整建堆

使用向下调整有一个前提：它的左右子树都是大/小堆，然后第一个和最后一个交换，但随机给你的数组并不能满足这个前提。

因此就有人想出了这么一个方法：从倒数第一个非叶子结点(最后一个结点的父亲)开始向下调整，直到根为止，因为叶子结点就它自己，天生就是堆，没有必要调整。

代码实现：

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
//2. 向下调整
void AdjustDown(int* heap, int father, int heapSize)
{
	int minchild = father * 2 + 1;
	while (minchild < heapSize)
	{
		if (minchild + 1 < heapSize && heap[minchild] > heap[minchild + 1])
		{
			++minchild;
		}
		if (heap[minchild] < heap[father])
		{
			Swap(&heap[father], &heap[minchild]);
			father = minchild;
			minchild = father * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* heap, int heapSize)
{
	//-1是最后一个结点的位置
	//再-1 / 2 就是父亲结点
	for (int i = (heapSize- 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(heap, i, heapSize);
	}
	//...排序 
}

int main()
{
	int arr[] = { 65,100,70,32,60,50 };
	int arrSize = sizeof(arr) / 4;
	HeapSort(arr, arrSize);
	return 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
38
39
40
41
42
43
44
45
46
47

以上就是两种建堆的方法，那么哪种方法效率更优呢？

实际上向上调整的时间复杂度为O(N*logN)，而向下调整的时间复杂度为O(N)，因此选择第二种方法更优，接下来证明一下两种方法的时间复杂度。

1.2 两种的调整算法的复杂度

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

1.2.1 向下调整的时间复杂度

高度为h，结点数量为N的完全二叉树
$2^h-1=N$
$h=lo{g}_2(N+1)$

第h层有2^h-1个节点，不需要调整，因为都是叶子结点，从倒数第二层开始调整。

每一层结点个数*这层结点最坏的向下调整次数

向下调整还有一个特点：结点数量越多，那么它调整的次数越少，反正，结点的数量越少，调整的次数就越多

因此：向下调整建堆的时间复杂度为O(N)。

---

1.2.2 向上调整的时间复杂度

与向下调整相反，向上调整的特点是：结点越少，调整次数越少，反之结点越多，调整次数越多。

所以说相比较向下调整而言，向上调整的效率不太高，因为最后一层结点就占了所有结点的一半(每层的结点个数是上一层的二倍)。

公式可以大致推导为：
$T(n)=2^1\ast 1+2^2\ast 2+2^3\ast \mathrm{3....}+2^{(h-2)}\ast (h-2)+2^{(h-1)}\ast (h-1)$

精确算用上面的错位相减法可以得到准确的时间复杂度，这里只大概的算一下复杂度。
大概算下来最后一层的复杂度就是N*logN了。

到这里不难发现向上调整不好的点就在这，最后一层占了一半的节点，并且每一个都要调整h-1次，效率太低，而向下调整最后一层结点都不参与调整，并且结点越多调整次数越少，所以建堆尽量都要使用向下调整建堆。

1.3 堆排的实现

了解了两种调整的基本情况后，接下来开始建堆，这时又出现两个问题：

1. 升序建大堆还是小堆？
2. 降序建大堆还是小堆？

结论：升序建大堆，降序建小堆。

如果升序建小堆的话，堆顶是最小的元素，那如何选出次小的元素呢？再次建堆选次小的话，建堆的时间复杂度是O(N)，选一个次小的建一次堆，那么排序的时间复杂度就是N²了，堆的优势就不在了。

而用大堆就可以很好的解决这个问题，这里要用到删除堆顶的思想。堆顶是最大的元素，把堆顶和最后一个元素交换，再把前N-1个元素看作是一个堆(交换后左右子树依然是大堆)，然后把堆顶元素进行向下调整选出次大的，后面依次重复这个步骤就完成了堆排序。

代码实现：

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//向下调整
void AdjustDown(int* heap, int father, int heapSize)
{
	int minchild = father * 2 + 1;
	while (minchild < heapSize)
	{
		if (minchild + 1 < heapSize && heap[minchild] < heap[minchild + 1])
		{
			++minchild;
		}
		if (heap[minchild] > heap[father])
		{
			Swap(&heap[father], &heap[minchild]);
			father = minchild;
			minchild = father * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* heap, int heapSize)
{
	//建大堆
	//-1是最后一个结点的位置
	//再-1 / 2 就是父亲结点
	for (int i = (heapSize - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(heap, i, heapSize);
	}

	int i = 1;
	while (i < heapSize)
	{
		//把第一个和最后一个交换，然后把前n-i个看成一个堆继续向下调整
		Swap(&heap[0], &heap[heapSize - i]);
		AdjustDown(heap, 0, heapSize - i);
		++i;
	}
}

int main()
{
	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
	int arrSize = sizeof(arr) / 4;
	HeapSort(arr, arrSize);
	for (int i = 0; i < arrSize; ++i)
	{
		printf("%d ", arr[i]);
	}
	return 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

以上就是整个堆排序的内容了。

2. TopK问题

2.1 什么是TopK

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

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

2.2 思路

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

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

2.3 代码实现

#include 
void TopK(const char* fileName, int k)
{
	//以读的方式打开文件
	FILE* fout = fopen(fileName, "r");
	if (!fout)
	{
		perror("fopen fail");
		exit(-1);
	}
	//创建k个数的小堆
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (!minHeap)
	{
		perror("fopen fail");
		exit(-1);
	}
	//先把文件中前k个数塞进数组中
	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", minHeap + i);
	}
	//向下调整建堆，此时建的小堆
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(minHeap, i, k);
	}
	//假设此时的堆中元素就是前k大的数，堆顶就是第k大
	//再把后N-k个数依次与堆顶的元素进行比较
	//比堆顶的数大就进堆
	//读到文件末尾时，堆里存放的就是前k大的数
	int val = 0;
	while (fscanf(fout, "%d", &val) != -1)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			AdjustDown(minHeap, 0, k);
		}
	}
}
void createDataFile(const char* fileName, int N)
{
	//调用时间戳
	srand((unsigned)time(NULL));	

	//以写的方式打开文件
	FILE* fin = fopen(fileName, "w");
	if (!fin)
	{
		perror("fopen fail");
		exit(-1);
	}
	//随机生成10000个数
	for (int i = 0; i < N; ++i)
	{
		fprintf(fin, "%d\n", rand() % 10000);
	}

	fclose(fin);
}
int main()
{
	const char* fileName = "data.txt";
	int N = 10000;
	int k = 6;

	//创建文件，随机生成10000个数
	createDataFile(fileName, N);

	//选出前k个大的数
	TopK(fileName, k);
	return 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

复杂度分析：建了k个数的堆，并且要比较后N-K个数，因此时间复杂度最坏为K + log*(N-K)，大概为O(N)，空间复杂度为O(K)，只用了k个额外空间。

---

本篇完