C语言实现用堆解决 TOP-K 问题

2023-04-18 117

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C语言实现用堆解决 TOP-K 问题

前言

生活中我们经常能见到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);
}

结果如下

完整源码

#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;
}

C语言实现用堆解决 TOP-K 问题

目录

前言

正文

TopK函数实现

如何测试

完整源码

热门文章

最新文章

相关课程

相关电子书