前言

在开始这一节的内容之前，我们先来回顾一下与堆相关的重点：

1、堆是二叉树顺序存储结构的一个具体体现，堆中每个节点的值总是不大于或不小于其父节点的值 (大堆/小堆)，堆总是一棵完全二叉树，堆使用顺序表存储元素；

2、堆中父节点下标的计算公式：(n-1)/2，左孩子下标：n*2+1，右孩子下标：n*2+2；

3、堆只能在尾部插入数据，且插入数据后需要保证堆的结构，所以在插入数据之后我们要进行向上调整，向上调整的时间复杂度为O(log N) (log 以2为底) ；

4、堆只能在头部删除数据，且删除数据后需要保证堆的结构，又因为顺序表头删需要挪动数据，效率很低，所以在堆删除数据会先将堆顶和堆尾的数据进行交换，然后让 size–，再进行向下调整，向下调整的时间复杂度为O(log N) (log 以2为底) 。

堆排序

堆排序是选择排序的一种，它的时间复杂度为 O(N*logN)，空间复杂度为 O(1)。

1、建堆

堆排序的第一步就是建堆，建堆有两种方法：向上调整建堆和向下调整建堆。

向上调整建堆： 把数组的第一个元素作为堆的根节点，然后在堆尾依次插入其余元素，每插入一个元素就向上调整一次，从而保证堆的结构；

向上调整建堆的时间复杂度： 由于堆是完全二叉树，而满二叉树是完全二叉树的一种，所以此处为了简化计算，使用满二叉树来得出时间复杂度 (时间复杂度本身看的就是近似值，多几个节点不影响最终结果)：

如上图，我们把每一次的节点个数除以每一个节点需要调整的次数，最后再求和，就可以得到一共需要调整的次数；然后再根据满二叉树节点总数与树的高度的关系将表达式中的h替换掉，最终可以得到向上调整建堆的时间复杂度为：O(N*logN)；

向下调整建堆： 从倒数第一个非叶子节点 (即最后一个叶节点的父节点) 开始向下调整，直到调整到根。

向下调整建堆的时间复杂度：

如上图，向下调整建堆的时间复杂度为：O(N)；

综合上面两种建堆方法，建堆的时间复杂度为：O(N)；

2、选数

现在我们建堆工作已经完成了，接下来就是选数，假设现在我们要排升序，那么方法一共有三种：

1、建小堆，开辟一个和原数组同等大小的新数组，每次取出堆顶的元素 (最小的元素) 放在新数组中，然后挪动数组中的数据，最后排好序以后再将新数组中的数据覆盖至原数组；

缺点：每次挪动数据的效率很低，且挪动数据会造成堆中其余元素父子关系混乱，需要重新建堆，而建堆的时间复杂度也是O(N)，所以二者嵌套后时间复杂度：O(N^2)，空间复杂度：O(N)；

2、也是建小堆，不过这次我们借鉴堆 pop 数据的方法，先将堆顶的元素放入新数组中，然后交换堆顶和堆尾的元素，之后再向下调整数组中前 n-1 个数据，直到排好序，最后将排好序以后再将新数组中的数据覆盖至原数组；

缺点：虽然此方法可以让我们每次都拿到数组中最小的元素，但是需要开辟额外的空间，时间复杂度：O(N*logN)，空间复杂度：O(N)；

3、建大堆，先将堆顶和堆尾的数据进行交换，使得数组中最大的元素处于数组末尾，然后向下调整前 n-1 个元素，使得次大的数据位于堆顶，最后重复前面的步骤，把次大的数据存放到最大的数据之前，直到数组有序；

优点：没有额外的空间消耗，且效率达到了 O(N*logN)；

综合上面三种选数的方法，选数的时间复杂度为：O(N*logN)，空间复杂度为：O(1)；

3、代码

//交换两个节点
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整 -- 大堆
void AdjustUp(int a[], int child)
{
	int parent = (child - 1) / 2;  //找出父节点

	while (child > 0)  //当调整到根节点时不再调整
	{
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
		}
		else
		{
			break;
		}

		//迭代
		child = parent;
		parent = (child - 1) / 2;
	}
}

//向下调整 -- 大堆
void AdjustDown(int a[], int n, int parent)
{
	int maxchild = parent * 2 + 1;  //找到左孩子（左孩子+1得到右孩子）

	while (maxchild < n)  //调整到数组尾时不再调整
	{
		if (maxchild + 1 < n && a[maxchild + 1] > a[maxchild])
		{
			maxchild += 1;
		}

		if (a[parent] < a[maxchild])
		{
			Swap(&a[parent], &a[maxchild]);
		}
		else
		{
			break;
		}

		//迭代
		parent = maxchild;
		maxchild = parent * 2 + 1;
	}
}

void HeapSort(int a[], int n)
{
	//建堆 -- 向上调整建堆：O(N*logN)
	//int i = 1;
	//for (i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}

	//建堆 -- 向下调整建堆：O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)  //n-1找到最后一个叶节点，该节点-1/2找到倒数第一个父节点
	{
		AdjustDown(a, n, i);
	}

	//排序 -- 升序（建大堆，向下调整）：O(N*logN)
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[i], &a[0]);  //交换堆尾和堆顶的元素
		AdjustDown(a, i, 0);  //向下调整
	}
}


int main()
{
	int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };
	int n = sizeof(a) / sizeof(a[0]);

	//堆排序
	HeapSort(a, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

---

TopK 问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大；比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

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

第一步：用数据集合中前K个元素来建堆 – 前k个最大的元素，则建小堆；前k个最小的元素，则建大堆；

第二步：用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素；

//交换两个节点
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整 -- 小堆
void AdjustDown(int a[], int n, int parent)
{
	int minchild = parent * 2 + 1;  //找到左孩子（左孩子+1得到右孩子）

	while (minchild < n)  //调整到数组尾时不再调整
	{
		if (minchild + 1 < n && a[minchild + 1] < a[minchild])
		{
			minchild += 1;
		}

		if (a[parent] > a[minchild])
		{
			Swap(&a[parent], &a[minchild]);
		}
		else
		{
			break;
		}

		//迭代
		parent = minchild;
		minchild = parent * 2 + 1;
	}
}

int* TopK(int a[], int n, int k)
{
	//开辟K个元素的空间
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	//将数组前K个元素拷贝到新空间
	for (int i = 0; i < k; i++)
	{
		minHeap[i] = a[i];
	}

	//建小堆 -- 向下调整建堆：O(N)
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)  //n-1找到最后一个叶节点，该节点-1/2找到倒数第一个父节点
	{
		AdjustDown(minHeap, k, i);
	}

	//取后N-k个元素与堆顶元素比较，如果大于堆顶元素，就入堆
	for (int i = k; i < n; i++)
	{
		if (minHeap[0] < a[i])
		{
			minHeap[0] = a[i];
			AdjustDown(minHeap, k, 0);
		}
	}
	return minHeap;
}

int main()
{
	int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };
	int n = sizeof(a) / sizeof(a[0]);

	//TopK问题 -- 前K个最大的元素
	int k = 3;
	int* ret = TopK(a, n, k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", ret[i]);
	}

	free(ret);
	ret = NULL;

	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
75
76
77
78
79
80
81
82
83
84
85
86

---