什么是Topk問題

其實顧名思義，這個問題也就是在N個數中找出前k個最值，在我們的日常生活中，很多地方都有Topk問題的影子，例如我們在點外賣時，總會說這家店是某某市的多少名，其實這些都是用Topk問題的解決方法得出來的，

方法一：堆排序法

這也是最容易想到的一種方法：我們可以將N個數排成有序的，然后輸出前k個最值，而在我們已學過的排序演算法中，堆排序的時間復雜度又是最快的（O（n*logn）），因此我們選擇了堆排序，

//交換函式
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下調整（小堆）
void AdjustDown(int* a, int n, int parent)
{
	//child記錄左右孩子中值較小的孩子的下標
	int child = 2 * parent + 1;//先默認其左孩子的值較小
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子還小
		{
			child++;//較小的孩子改為右孩子
		}
		if (a[child] < a[parent])//左右孩子中較小孩子的值比父結點還小
		{
			//將父結點與較小的子結點交換
			Swap(&a[child], &a[parent]);
			//繼續向下進行調整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	int i = 0;
	//建小堆
	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, arrSize, i);
	}
	//排降序
	int end = arrSize - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
	//將最大的k個數存入陣列
	int* retArr = (int*)malloc(sizeof(int)*k);
	for (i = 0; i < k; i++)
	{
		retArr[i] = arr[i];
	}
	return retArr;//回傳最大的k個數
}

時間復雜度：O(N+NlogN)?空間復雜度：O(N)，能否將其再優化了？肯定是可以的，下面看方法二，

方法二：把N個數建堆，取出前k個

這種方法其實也不難想到，我們利用了堆的性質：堆的0號位一定是最值，小堆則為最小值，大堆則為最大值，

注意點：
1.取出資料后要讓其與最后的元素替換，因為你已經取出這個元素了，所以不需要它了，這時讓它去堆尾，不讓它算入堆的個數中就行了，為什么要這樣做了，因為這樣既保證了堆的結構，也相當于把這個取出來的數洗掉了，
2. 如果在取到堆頂資料后直接洗掉資料，那么就要重新建堆了，正確的做法應該是上面所說的方法，因為那樣只要進行一次向下調整，就可以保證堆的結構了，要知道建堆的復雜度為O(N),而一次向下調整的復雜度僅為O（logn），這樣大大提升了效率，

//交換函式
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下調整（大堆）
void AdjustDown(int* a, int n, int parent)
{
	//child記錄左右孩子中值較大的孩子的下標
	int child = 2 * parent + 1;//先默認其左孩子的值較大
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子還大
		{
			child++;//較大的孩子改為右孩子
		}
		if (a[child] > a[parent])//左右孩子中較大孩子的值比父結點還大
		{
			//將父結點與較大的子結點交換
			Swap(&a[child], &a[parent]);
			//繼續向下進行調整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	int i = 0;
	//建大堆
	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, arrSize, i);
	}
	//將最大的k個數存入陣列
	int* retArr = (int*)malloc(sizeof(int)*k);
	int end = arrSize - 1;
	for (i = 0; i < k; i++)
	{
		retArr[i] = arr[0];//取堆頂資料
		Swap(&arr[0], &arr[end]);//交換堆頂資料與最后一個資料
		//進行一次向下調整，不把最后一個資料看作待調整的資料，所以待調整資料為end=arrSize-1
		AdjustDown(arr, end, 0);
		end--;//最后一個資料的下標改變
	}
	return retArr;//回傳最大的k個數
}

時間復雜度：O（n+k*logn），空間復雜度：O（n），那么問題來了，萬一n是一個特別大的數字了，那效率依舊不是很高，有沒有更快的方法了？下面我們來看看方法三，

方法三：建一個k個數的堆

我們以找出最大的k個數為例，該方法為：先建一個k個數的小堆，然后將陣列中n-k個元素依次與堆頂的元素比較，若比堆頂元素大，則將堆頂元素洗掉，然后將這個數插入到堆中，這兒要注意：插入這個數到堆中的時候，要使用向上排序演算法保證堆的結構不被破壞，到最后，堆里面的k個數就是最大的k個數了，

那么問題來了，上面的例子中為什么不用大堆了，不是選最大的k個數嗎？其實這很容易理解，我們假設一下，如果建一個大堆，萬一堆頂的資料就是n個數中最大的那個，那么不論怎么比較，你后面的n-k個元素都沒法進堆，因此要用小堆來解決這個問題，

void PrintTopK(int* a, int n, int k)
{
	Hp hp;
	HpInit(&hp, a, k);
	int i = k;
	for (i = k; i < n; i++)
	{
		if (a[i]>HpTop(hp))
		{
			HpPop(&hp);
			HpPush(&hp, a[i]);
		}
	}
	//你此時資料改變之后是在堆里面的，你列印a沒用啊
	//for (i = 0; i < k; i++)
	//{
	//	printf("%d ", a[i]);
	//}
	for (i = 0; i < k; i++)
	{
		printf("%d ", HpTop(hp));
		HpPop(&hp);
	}
	printf("\n");
}

時間復雜度：O（k+n*logk） 空間復雜度：O（n） 與之前兩種方法對比，這種方法大大提高了效率，