『初阶数据结构 • C语言』⑭ - C语言实现用堆解决 TOP-K 问题_c语言topk问题减治法代码

目录

TopK函数实现

如何测试

完整源码 

---

生活中我们经常能见到TopK问题，例如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

所以，TopK问题即求出一组数据中前K个最大或最小的元素，一般情况下，数据量都比较大。

对于TopK问题，我们首先想到的可能是排序，对数据排好序以后，取前K个元素。但是，面对庞大的数据量时，排序并不适用，因为加载庞大的数据到内存中是个不小的消耗。

所以，对于TopK问题，最佳的解决方式是用堆。

思路如下：

1.取数据前K个元素来建堆；

若要求前K个最大的元素，则建小堆；

若要求前K个最小的元素，则建大堆；

2.用剩余的N-K个元素依次与堆顶元素进行比较，若大于堆顶元素，则赋值给堆顶元素，并向下调整。（取前K个最小元素则是小于）。

将剩余N-K个元素依次与堆顶元素比较完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

此算法的时间复杂度为 O(N*log K)。

TopK函数实现

void PrintTopK(int* a, int n, int k)
{
	Heap hp;
    //初始化堆
	HeapInit(&hp);
	
	//对数组的前K个元素进行建堆
	HeapCreate(&hp, a, k);
 
	//依次比较剩余N-K个元素与堆顶元素
	for (int i = k; i < n; i++)
	{
		if (a[i] > hp.a[0])
		{
			//若大于则赋值
			hp.a[0] = a[i];
		}
		//向下调整
		AdjustDown(hp.a, k, 0);
	}
 
	//打印堆中的K个元素，即为TopK的元素
	for (int i = 0; i < k; i++)
	{
		printf("%d ", hp.a[i]);
	}
}

如何测试

生成1000个小于1000000的随机数，将其中10个修改为大于1000000的数，若程序执行后可以得到这10个数，即测试成功。

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}

结果如下：

完整源码 

若对堆的知识不太了解，没关系，这里为你准备了简要但透彻的堆的讲解⇢二叉树的顺序结构——堆的概念&&实现（图文详解+完整源码 | C语言版）

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>
 
typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;   //存储数据
	int size;				//堆有效数据的大小
	int capacity;			//堆的容量
}Heap;
 
//给出一个数组，对它进行建堆
void HeapCreate(Heap* php, HPDataType* a, int n);
//堆的初始化
void HeapInit(Heap* php);
//对申请的内存释放
void HeapDestroy(Heap* php);
//添加数据
void HeapPush(Heap* php, HPDataType data);
//删除数据
void HeapPop(Heap* php);
//向上调整算法
void AdjustUp(HPDataType* a, int child);
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
//打印堆的数据
void HeapPrint(Heap* php);
//判断堆是否为空
bool HeapEmpty(Heap* php);
//返回堆的大小
int HeapSize(Heap* php);
//返回堆顶的数据
HPDataType HeapTop(Heap* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
 
 
void PrintTopK(int* a, int n, int k)
{
	Heap hp;
	HeapInit(&hp);
	
	//对数组的前K个元素进行建堆
	HeapCreate(&hp, a, k);
 
	//依次比较剩余N-K个元素与堆顶元素
	for (int i = k; i < n; i++)
	{
		if (a[i] > hp.a[0])
		{
			//若大于则赋值
			hp.a[0] = a[i];
		}
		//向下调整
		AdjustDown(hp.a, k, 0);
	}
 
	//打印堆中的K个元素，即为TopK的元素
	for (int i = 0; i < k; i++)
	{
		printf("%d ", hp.a[i]);
	}
}
 
void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}
 
int main()
{
	TestTopk();
	return 0;
}
 
void HeapCreate(Heap* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//将数组的内容全部拷贝到堆中
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
 
	//建堆算法
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
}
 
void HeapInit(Heap* php)
{
	assert(php);
 
	php->a = NULL;
	php->size = php->capacity = 0;
}
 
void HeapPrint(Heap* php)
{
	assert(php);
 
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
}
 
void HeapDestroy(Heap* php)
{
	assert(php);
 
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
 
void HeapPush(Heap* php, HPDataType data)
{
	assert(php);
	//如果容量不足就扩容
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
 
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	//添加数据
	php->a[php->size] = data;
	php->size++;
	//将新入堆的data进行向上调整
	AdjustUp(php->a, php->size - 1);
}
 
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
 
	//将堆顶的数据与堆尾交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	//将此时堆顶的data向下调整
	AdjustDown(php->a, php->size, 0);
}
 
void AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	//先默认较大的为左孩子
	int child = parent * 2 + 1;
	while (child < n)
	{
		//如果右孩子比左孩子大，就++
		if (a[child] > a[child + 1] && child + 1 < n)
		{
			child++;
		}
		//建大堆用'>'，小堆用'<'
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
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;
		}
	}
}
 
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
 
	return php->a[0];
}
 
int HeapSize(Heap* php)
{
	assert(php);
 
	return php->size;
}
 
bool HeapEmpty(Heap* php)
{
	assert(php);
 
	return !php->size;
}
 
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *(p1);
	*(p1) = *(p2);
	*(p2) = tmp;
}