数据结构-用堆解决Top-K问题

2023-12-29 20:05:16

应用背景

应用背景

生活中我们每每都会遇到Top-K问题，例如搜索附近前几的的动漫，频率前几的搜索词条等等

示例：

如果只是数据比较少的，我们可以排序找到前几的数据，但是实际应用中我们时常都会面对海量的数据，大到内存无法全部加载，这就需要我们用数据结构中的堆来解决

处理策略

首先我们知道：

对于大堆，堆顶的数据一定是堆里面数据中最大的；对于小堆，堆顶的数据一定是堆里面数据中最小的

对于找最大前k：

利用小根堆维护一个大小为K的数组，目前该小根堆中的元素是排名前K的数，其中根是最小的数

此后，每次从数据中取一个元素与根进行比较，如大于根的元素，则将根元素替换并进行向下调整（下沉）

即保证小根堆中的元素仍然是排名前K的数，且根元素仍然最小（否则不予处理）

时间复杂度

总结：该算法的时间复杂度是(nlogk)

首先需要对K个元素进行建堆，时间复杂度为O(k)

建堆复杂度证明：

然后要遍历数据,最坏的情况是每个元素都与堆顶比较并排序，需要堆化n次

每次最差都下调高度次，而高度为log（k），所以是O(nlog(k))

因此总复杂度是O(k+nlog(k))，也就是O(nlogk)

过程及实现代码

图示过程：

参考代码：

// TopK问题：找出N个数里面最大/最小的前K个问题
// 找最大的前K个，建立K个数的小堆
// 找最小的前K个，建立K个数的大堆
void PrintTopK(int* a, int n, int k)//对大的前K
{
	HP hp;
	HeapInit(&hp);

	for (int i = 0; i < k; i++)//建立一个小堆
	{
		HeapPush(&hp, a[i]);
	}
	for (int i = k; i < n ; i++)
	{
		if (HeapTop(&hp) < a[i])//比较和调整（维护堆，保证始终是最大的前K）
		{
			hp.a[0] = a[i];
			AdjustDown(hp.a, k, 0);
		}
	}
	HeapPrint(&hp);
}

测试

测试代码：

void TestTopk()
{
	int n = 1000000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)//产生一万个数据
	{
		a[i] = rand() % 1000000;//都比100w小的数
	}
	// 再去设置10个比100w大的数（随机设置）
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[5355] = 1000000 + 3;
	a[51] = 1000000 + 4;
	a[15] = 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 <stdbool.h>

//默认堆中的数据类型
typedef int HPDataType;
//堆结构体类型
typedef struct Heap
{
	HPDataType* a;//数组指针（指向动态开辟的空间）
	int size;//堆中存放的数据个数
	int capacity;//堆的容量（数组长度）
}HP;
//堆初始化
void HeapInit(HP* hp);
//堆销毁
void HeapDestroy(HP* hp);
//入堆
void HeapPush(HP* hp, HPDataType x);
//出堆
void HeapPop(HP* hp);
//堆数据打印
void HeapPrint(HP* hp);
//堆顶数据
HPDataType HeapTop(HP* hp);
//堆存入数据个数
int HeapSize(HP* hp);
// 堆的判空
bool HeapEmpty(HP* hp);
//交换函数
void Swap(HPDataType* a, HPDataType* b);
//数据调整(实现大堆)
void AdjustUp(HPDataType* a, int child);
//数据调整
void AdjustDown(HPDataType* a, int size, int parent);

//堆初始化
void HeapInit(HP* hp)
{
	assert(hp);//避免传入参数错误
	//初始化
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
//堆销毁
void HeapDestroy(HP* hp)
{
	assert(hp);//避免传入参数错误
	//释放
	free(hp->a);
	hp->capacity=hp->size=0;
}
//数据调整
void AdjustUp(HPDataType* a, int child)//
{
	int parent = (child - 1) / 2;
	while (child)
	{
		if (a[parent] > a[child])//不符合情况交换
			Swap(&a[parent], &a[child]);
		else
			break;

		//调整下标
		child = parent;
		parent = (child - 1) / 2;
	}
}
//数据调整
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 HeapPush(HP* hp, HPDataType x)
{
	assert(hp);//避免传入参数错误
	//满堆的情况
	if (hp->size == hp->capacity)
	{
		//如果容量为0则开辟4个空间，否则扩展成原来的两倍
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HP* tmp = (HP*)realloc(hp->a, sizeof(HP) * newcapacity);
		if (tmp == NULL)//开辟失败则打印错误并结束进程
		{
			perror("realloc fail:");
			exit(-1);
		}
		hp->capacity = newcapacity;
		hp->a = tmp;
	}
	//入堆操作
	hp->a[hp->size] = x;//入尾端，再调整
	hp->size++;

	//数据调整
	AdjustUp(hp->a, hp->size - 1);//传入数组地址和下标
}
//出堆（删除堆顶的数据）
void HeapPop(HP* hp)
{
	assert(hp);//避免传入参数错误
	assert(hp->size);//空堆的情况
	
	Swap(&hp->a[0], &hp->a[hp->size - 1]);//先将堆顶数据与堆尾交换
	hp->size--;//再将记录数据个数变量减减实现删除的效果

	//对现在堆顶的数据进行下调
	AdjustDown(hp->a, hp->size, 0);
}
//堆数据打印
void HeapPrint(HP* hp)
{
	assert(hp);//避免传入参数错误

	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}printf("\n");
}
//堆存入数据个数
int HeapSize(HP* hp)
{
	assert(hp);//避免传入参数错误

	return hp->size;
}
// 堆的判空
bool HeapEmpty(HP* hp)
{
	assert(hp);//避免传入参数错误

	return hp->size==0;
}
//交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

有问题欢迎留言，可以的话留下你的三连哦！

码农公寓

应用背景

处理策略

时间复杂度

过程及实现代码

测试

堆源码

相关文章