【数据结构】堆排序和Top-k问题

文中一些函数的实现请参考【数据结构】堆

堆结构是一种非常实用的工具，它在解决某些特定问题时能够发挥出极高的效率。本文将探讨堆结构在堆排序和Top-k问题中的应用，通过深入剖析这两个问题，我们可以更好地理解堆结构的性质和使用方法。

堆排序

如果只是将待排数组建立一个大堆或者小堆是无法得到一个升序或者降序的数组，因为对与一个堆，我们没法知道同一层的大小关系。

但是，如果建立了一个大堆，那么堆顶元素一定是这个数组中最大的，那么将堆顶元素删除（并不是真的删除，而是放在数组最后）用其余元素再次建立一个堆，那么这个新堆的堆顶元素就是剩余元素中的最大值，不断循环则个操作不就可以得到一个升序的数组。

• 升序建大堆
• 降序建小堆

降序排列为例

代码实现

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void sort(int a[], int n)
{
	for (int i = 1; i < n; i++)//建小堆
	{
		ShiftUp(a, n, i);
	}
	for (int j = 1; j < n; j++)
	{
		swap(&a[0], &a[n - j]);
		ShiftDown(a, n - j, 0);//每次将堆顶的元素（数组末端的交换值）向下移动重新建小堆
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度

• 平均时间复杂度：O(nlogn)
• 最佳时间复杂度：O(nlogn)
• 最差时间复杂度：O(nlogn)
• 稳定性：不稳定

Top-K问题

什么是Top-K问题

给一个无序的数组，长度为N， 请输出最小 （或最大）的K个数。

Top-K问题的求解思路

1. 将前k个元素建堆
   • 如果求最大就建小堆，如果求最小建大堆
2. 将剩余n-k个元素依次和堆顶元素比较，不满足某个条件就替换
   • 某个条件是：如果求前K个最大元素，则是堆顶元素小于剩余元素，如果求前K个最小元素，则是大于剩余元素

为什么求前K个最大的元素要建小堆

举一个简单的例子，在1,2，3,4，5,6，7中求前3个最大元素
求解步骤如下

1. 前三个元素1,2，3建立一个小堆
   
2. 4和小堆堆顶元素比较，替换堆顶元素1，重新建堆（2,4，3）
   
3. 5和小堆堆顶元素比较，替换堆顶元素2，重新建堆（3,4，5）
4. 6和小堆堆顶元素比较，替换堆顶元素3，重新建堆（4,6，5）
5. 7和小堆堆顶元素比较，替换堆顶元素4，重新建堆（5,6，7）

替换的过程就是将原来堆中最小的元素剔除掉，换一个较大的元素进去，不断重复这个过程，这个堆中最小的元素越来越大，那么最后也只有第k大的元素可以替换掉这个堆中最小的元素，那么就求出了前K个最大的元素

代码实现

以求前K个最大元素为例

void TOPK(int*a,int n,int k)
{
	for (int i = (k - 1) / 2; i >= 0; i--)
	{
		ShiftDown(a, k, i);
	}
	for (int i = k; i < n; i++)
	{
		if (a[i] > a[0])
		{
			int temp = a[i];
			a[i] = a[0];
			a[0] = temp;
			for (int i = (k - 1) / 2; i >= 0; i--)
			{
				ShiftDown(a, k, i);
			}
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}
	
}
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

总结
本文通过对堆排序和Top-k问题的探讨，展示了堆结构在数据处理中的强大作用。堆排序利用堆的性质，能够在O(nlogn)的时间复杂度下完成排序，而Top-k问题则可以通过维护一个小顶堆来解决，时间复杂度为O(nlogk)。通过对这两个问题的分析，我们可以看到堆结构在解决问题时的高效性和灵活性。希望本文的内容能够帮助读者更好地理解和应用堆结构。