數(shù)據(jù)結(jié)構(gòu) | TOP-K問題

TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。

就是從N個數(shù)里面找最大前K個（N遠大于K）

思路一：

• N個數(shù)插入到堆里面，PopK次

時間復(fù)雜度是O(N*logN) + K*logN == O(N*logN)

• N很大很大，假設(shè)N是100億，K是10
  100億個整數(shù)大概需要40G左右

所以這個思路很不好~~

思路二：

• 讀取前K個值，建立K個數(shù)的小堆
  依次再取后面的值，跟堆頂比較，如果比堆頂大，替換堆頂進堆（替換對頂值，再向下調(diào)整）

時間復(fù)雜度是O(N*logK)

隨機生成一些數(shù)據(jù)，找前k個最大值

• 那么我們就先要造數(shù)據(jù)，隨機生成

void CreateData()
{
	//造數(shù)據(jù)
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 100000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

• 打開項目的源文件所在的文件夾，就會有這個data.txt的文件，里面已經(jīng)隨機生成了10萬個數(shù)字

進行取前k個值建堆

• 我們先從文件中讀數(shù)據(jù)
• 然后取前k個進行建立一個小堆
• 讀取前k個數(shù)，邊讀邊建立小堆
• 如果讀取的整數(shù) x 大于堆頂元素，將堆頂元素替換為 x，然后進行向下調(diào)整

void PrintTopK(const char* file, int k)
{
	//讀文件
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	//建立一個k個數(shù)的小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}

	//讀取前k個數(shù)
	//邊讀邊建小堆
	/*for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		AdjustUp(minheap, i);
	}*/
	
	// 建小堆
	for (int i = (k-1-1)/2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}
	//讀取剩余的值，讀到x里
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			//向下調(diào)整
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	
	free(minheap);
	fclose(fout);
}

找到了前k個結(jié)果以及全部代碼

• 比如我取前5個最大的，我們來看一下結(jié)果

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
			++child;
		
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void CreateData()
{
	//造數(shù)據(jù)
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 100000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}


void PrintTopK(const char* file, int k)
{
	//讀文件
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	//建立一個k個數(shù)的小堆

	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}

	//讀取前k個數(shù)
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		//向上調(diào)整
		AdjustUp(minheap, i);
	}

	//邊讀邊建小堆
	//讀取剩余的值，讀到x里
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		//如果堆里的元素小于x就繼續(xù)調(diào)整
		if (minheap[0] < x)
		{
			//將x搞到堆頂
			minheap[0] = x;
			//向下調(diào)整
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}

	free(minheap);
	fclose(fout);
}

int main()
{
	//CreateData();
	PrintTopK("data.txt",5);

	return 0;
}

• 那么我們知道這前5個是最大的嗎？

• 這個時候就要加入我們的密探，手動從文件里加入5個最大的數(shù)~~

  • 加入這幾個數(shù)100001 100002 100003 100005 100004
  • 然后再執(zhí)行代碼，可以看到已經(jīng)完美的出來了~~

文章來源地址http://www.zghlxwxcb.cn/news/detail-751857.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) | TOP-K問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！