TopK問題

gitee上有更詳盡的代碼：堆 + TopK代碼

文章目錄

TopK問題
- 一、問題分析
- - 1. 方法一
  - 2. 方法二
  - 3. 方法三
- 二、TopK實作
- - 1. 前k個數的小堆
  - 2. n-k個數和根去比較
  - 3. 列印堆
- 三、測驗

topk問題就是取n個資料中，找出最大/最小的前k個數

一、問題分析

1. 方法一

對n個資料進行排序，再取出前k個元素

時間復雜度：O(N * logN)

2. 方法二

將n個資料依次插入大堆，然后pop堆的根 k 次

時間復雜度：O(N + k * logN)

設有n個資料，有log2(n + 1)層，最壞的情況就是每個資料要向上調整k次

3. 方法三

如果n很大，記憶體中無法儲存，插入堆和排序的方法都不行

用前K個數建立一個K個數的小堆
剩下的N-K個數,依次跟堆頂的資料進行比較如果比堆頂資料大，就替換堆頂的資料，再向下調整
最后堆里面K個數就是最大的K個數

原理：

在方法二的基礎上，大堆實作不了，但小堆卻能很好的實作

小堆的優點就是，根是堆中所有元素中最小的元素，我們建立一個小堆，可以存放k個數，后面n-k個數字再與之比較，這樣就能把小數pop出來，把大數push進去

可能會擔心：

如果小堆里正好都是我們想要的數怎么辦？

那與之比較的n-k的數肯定沒有比根更大的數了
如果這里小堆換成大堆？

那可能根是最大的數字，沒法操作了，小的話放進去，那如果不是前k個大的數字就進去了，亂套了

時間復雜度：O(k + (n-k)*logk)

二、TopK實作

本篇在上一章：【資料結構】堆_Rinne’s blog-CSDN博客

寫了幾個二叉樹常用的插口

gitee上有更詳盡的代碼：堆 + TopK代碼

1. 前k個數的小堆

//定義和初始化堆
Heap hp;
HeapInit(&hp);

int i = 0;
//k個數的小堆
for (i = 0; i < k; i++)
{
	//插入k個資料
	HeapPush(&hp, a[i]);
}

2. n-k個數和根去比較

在這里插入圖片描述

比它大，替換

在這里插入圖片描述

再向下調整

在這里插入圖片描述

//k - n 個數與根作對比
for (i = k; i < n; i++)
{
	if (a[i] > HeapTop(&hp))
	{
		hp.a[0] = a[i];
		AdjustDown(hp.a, hp.size, 0);
	}
}

3. 列印堆

//列印堆
void HeapPrint(Heap* hp, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

三、測驗

測驗代碼：

這里用到了srand函式和time函式以及rand函式，用來生成亂數值

更多有關亂數生成的詳細知識可以參考文章：C語言亂數生成教程

void TestTopk()
{
	//一共有20個數字
	int n = 20;
	int* a = (int*)malloc(sizeof(int) * n);
	assert(a);

	srand((unsigned int)time(NULL));
	
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 10;
	}
	// 再去設定5個比10大的數
	a[5] = 10 + 1;
	a[11] = 10 + 2;
	a[15] = 10 + 3;
	a[1] = 10 + 4;
	a[10] = 10 + 5;

	PrintTopK(a, n, 5);


}