TOP-K+文件

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

建堆N个的大堆，pop前K个。假设有十亿整型数据（1G约等于10亿Byte）

先建立一个K个数的小堆。再遍历其余数据，若遍历到的数据比堆顶数据大，就代替他进堆到堆顶。再向下调整，大的数就沉到了堆底。

创建数据文件

文件的使用

  1. 打开文件：要打开文件，你可以使用fopen函数。它接受两个参数：**文件名和打开模式。**打开模式可以是读取（”r”）、写入（”w”）、追加（”a”）等。例如：

    1
    FILE* file = fopen("example.txt", "r"); // 以只读模式打开文件

    这将打开名为 "example.txt" 的文件以供读取。

  2. 读取文件：使用fread、fscanf或fgets等函数来从文件中读取数据。例如，使用fscanf读取整数：

    1
    fscanf(file, "%d", &num);

    这将从文件中读取一个整数并将其存储在变量 num 中。

  3. 写入文件：使用fwrite、fprintf或fputs等函数将数据写入文件。例如，使用fprintf写入字符串：

    1
    fprintf(file, "Hello, World!\n");

    这将字符串 “Hello, World!” 写入文件。

  4. 关闭文件：完成文件操作后，使用fclose函数关闭文件，以释放相关资源：

    1
    fclose(file);

    关闭文件后，不再能够对其进行读取或写入操作。

1
2
3
4
5
6
7
8
/*创建文件*/
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
	perror("fopen failed");
	return;
}

生成随机数

利用种子生成伪随机数

1
2
3
4
5
6
7
/*生成并写入随机数*/
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
	int x= rand() % 10000;//控制数据在一万以内
	fprintf(fin, "%d\n",x);
}

向下调正建立小堆

理解向下调整的原理：传入下标最大的父辈（倒数第二行的数据），通过与其子代比较，交换数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*--向下调整-建立小堆--*/
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])//右孩子小于左孩子的情况，需要找到最小的孩子要检查是否一定有右孩子
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

完整源码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<time.h>
typedef int HPDataType;

/*-简单的交换函数-*/
void Swap(HPDataType* p1, HPDataType* p2)//交换函数
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

/*--向下调整-建立小堆--*/
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])//右孩子小于左孩子的情况，需要找到最小的孩子要检查是否一定有右孩子
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

/*读取数据并输出最大的前k个数据*/
void TopK(const char*file,int k)
{
	/*建堆-用文件前k个元素建堆*/
	int *topk= (int*)malloc(sizeof(int) * k);//创建大小为k的数组，逻辑结构为堆
	assert(topk);

	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen failed");
		return;
	}

	/*读出前k个数建立一个小堆*/
	for(int i=0;i<k;i++)
	{
		fscanf(fout, "%d", &topk[i]);
	}

	for (int i = (k - 2) / 2; i >= 0; --i)//i = (k - 2) / 2是第一个父辈的下标
	{
		AdjustDown(topk, k, i);
	}

	/*将剩余n-k个元素依次与堆顶元素交换*/
	int val = 0;
	int ret = fscanf(fout, "%d", &val);
	while (ret != EOF)
	{
		if (val > topk[0])
		{
			topk[0] = val;
			AdjustDown(topk, k, 0);//交换并向下调整，使得顶部的数据最小
		}
		ret = fscanf(fout, "%d", &val);
	}

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

/*创建n个随机数据，存写在文件中*/
void CreatTopk()
{
	int n = 20;//数据的数量

	/*创建文件*/
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen failed");
		return;
	}
	
	/*写入随机数*/
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		int x= rand() % 10000;//控制数据在一万以内
		fprintf(fin, "%d\n",x);
	}

	fclose(fin);

}

int main()
{
	CreatTopk();
	TopK("data.txt", 10);
	return 0;
}