Topk问题-代码

数据写入文件

void CreateNDate()
{
	FILE* fin = fopen("text.data", "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 10000; i++)
	{
		int ret = (rand() + i)%10000;//+i是为了减少数据的重复，%10000是为了控制数据的范围
		fprintf(fin, "%d\n", ret);
	}
	fclose(fin);
}

建堆

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

int k = 0;
printf("请输入k:");
scanf("%d", &k);
int* kminheap = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++)
{
	fscanf(fout, "%d", &kminheap[i]);
}
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(kminheap, k, i);
}

数据之间的比较

int x = 0;
while (fscanf(fout, "%d", &x)>0)
{
	if (x > kminheap[0])
	{
		kminheap[0] = x;
		AdjustDown(kminheap, k, 0);
	}
}

完整代码

int k = 0;
printf("请输入k:");
scanf("%d", &k);
int* kminheap = (int*)malloc(sizeof(int) * k);
if (kminheap == NULL)
{
	perror("malloc fail");
	return;
}
FILE* fout = fopen("text.data", "r");
if (fout == NULL)
{
	perror("fopen fail");
	return;
}
for (int i = 0; i < k; i++)
{
	fscanf(fout, "%d", &kminheap[i]);
}
//建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(kminheap, k, i);
}
int x = 0;
while (fscanf(fout, "%d", &x)>0)
{
	if (x > kminheap[0])
	{
		kminheap[0] = x;
		AdjustDown(kminheap, k, 0);
	}
}
for (int i = 0; i < k; i++)
{
	printf("%d ", kminheap[i]);
}