堆的应用：堆排序和TOP-K问题

堆的应用

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

利用堆删除的思想来进行排序。以升序为例，建立大根堆后，交换堆顶和堆末尾的数据并减少堆的长队，再利用向下调整算法重新建立堆。这样最大的数据就成功到数组末尾了。

HeapSort的代码：

void HeapSort(int* 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--;
	}
}

堆排序使用堆来选数，效率较高。
时间复杂度：O(N*logN)；
空间复杂度：O(1)
稳定性：不稳定

TOP-K问题

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

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

1. 用数据集合中前K个元素来建堆。要求前k个最大的元素，则建小堆；前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素（这样需要开辟的数组大小仅仅是K了，节省了空间）

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

TOP-K问题代码：

void PrintTopK(int* a, int n, int k)
{
    
	//找大数建小堆
	//建堆 用a中前k个元素建堆
	int* kMinHeap = (int*)malloc(sizeof(int) * k);
	if (kMinHeap == NULL)
	{
    
		printf("malloc fail\n");
		exit(-1);
	}
	for (int i = 0; i < k; i++)
	{
    
		kMinHeap[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
    
		AdjustDown(kMinHeap, k, 0);
	}

	//将剩余n-k个元素一次与堆顶元素交换，不满则替换
	for (int j = k; j < n; j++)
	{
    
		if (a[j] > kMinHeap[0])
		{
    
			kMinHeap[0] = a[j];
			AdjustDown(kMinHeap, k, 0);
		}
	}

	for (int j = 0; j < k; j++)
	{
    
		printf("%d ", kMinHeap[j]);
	}
	printf("\n");
}