目录
生活中我们每每都会遇到Top-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;
}
有问题欢迎留言,可以的话留下你的三连哦!