备案控制台
开发者社区 人工智能 文章 正文

数据结构之堆的应用

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

在我们学习了堆之后我们知道，无论是大堆还是小堆，堆顶的元素要么最大，要么最小。

对于堆插入的时间复杂度为O（logn）也就是向上调整算法的复杂度，删除一个堆中的元素为O（logn），堆在我们日常生活中还是常用到的。

1.top k问题（优质筛选问题）

什么是top k问题？即求数据结合中前k个最大元素或最小元素，一般情况下数据量较大。

假设N是100万，k是100，求100 万中的前10个最大数，当数足够大，排序已经无法实现了，空间太大，无法内存中开辟，在磁盘上开辟（但磁盘中无法建堆），而且磁盘运行速度很慢。

如：求得大量数字中的前k个大或前k个小的数，普通的算法时间复杂度较高，效率较慢，数量太大，无法寻找。利用堆的特性，算法效率高，面对数量大的数据也适用。

1.用数据集合中前k个元素来建堆。

前k个最大元素  建大堆

前k个最小元素  建小堆


c327611d9259434cad2b8de0b64e51a1.png 我们这里设置随机数10个，这里你可以改变，越大越能体现堆的功能，找出其中的最大五个，

思路就是先读取五个数进入数组里，之后再从第k+1个数开始与堆顶比较，比堆顶大就替换，每一次都要向下调整，确保是一个小堆，到最后最大的五个数就是小堆的五个数，第一个是五个里最小的。

#include<stdlib.h> 
#include<stdio.h>
#include<time.h>
void Adjustdown1(int* 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])
    {
      //交换
      int tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void creatnDATA()
{
  int n = 10;
  srand(time(NULL));
  const char* file = "data.txt";
  FILE* fp = fopen(file, "w");
  if (fp == NULL)
  {
    perror("fopen fail");
    return;
  }
  for (size_t i = 0; i < n; i++)
  {
    int x = rand() % 100000;
    fprintf(fp, "%d\n", x);
  }
  fclose(fp);
}
void printtopk(int k)
{
  const char* file = "data.txt";
  FILE* fp = fopen(file, "r");
  if (fp == NULL)
  {
    perror("fopen fail");
    return;
  }
  int* kminheap = (int*)malloc(sizeof(int) * k);
  //从文件中读k个数
  for (size_t i = 0; i < k; i++)
  {
    fscanf(fp, "%d", &kminheap[i]);
  }
  //建小堆
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    Adjustdown1(kminheap, k, i);
  }
  int val = 0;
  //比较 ,如果比堆顶大，则需要交换，之后再向下调整。
  while (!feof(fp))
  {
    //从第k+1个数处再开始读
    fscanf(fp, "%d", &val);
    //val用来存放读的数 
    if (val > kminheap[0])
    {
       kminheap[0]=val;
      Adjustdown1(kminheap, k, 0);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", kminheap[i]);
  }
  printf("\n");
}
int main()
{
  creatnDATA();
  printtopk(5);
  return 0;
}

2.堆排序

正常的思维，所谓对堆排序就是用堆这个数据结构来实现排序，思路也很简单，取堆头存入数组，向下调整，在出堆，循环往复。

如下，在有堆的前提，我们可以实现堆排序：

//前提有堆的实现
void heapsort(int *a,int n)
{
  HP f;
  Heapinit(&f);
  for (int i = 0; i < n; i++)
  {
    Heappush(&f, a[i]);
  }
      int i = 0;
  while (!HeapEmpty(&f))
  {
    //进行排序
    int top = HeapTop(&f);
    a[i++] = top;
    Heappop(&f);
  }
}
int main()
{
  int a[] = {10,6,9,3,5,7,65};
  heapsort(a,sizeof(a)/sizeof(int));
  for (int i=0; i < sizeof(a) / sizeof(int); i++)
  {
    printf("%d ", a[i]);
  }
}

但我们也会发现其空间复杂度较高，需要拷贝数据，虽然这个堆排序效率还行，但是我们又看到想要以这种方法实现我们还的需要实现堆的所有操作！！！！这太麻烦了，那这种排序又有谁会用呢？

实则不然，真正的堆排序是利用堆的思路，我们是把传进来这个数组直接建堆，省去一部分操作，提高效率。因此建堆又有两种方式：

1.向上调整建堆

给出排序的数组，以此来建堆，根据堆的结构  

建小堆-----最后排序为降序


c4af32149fc1459db7faef6142eb4e6e.png

void Adjustup1(HPDATAtype* a, int child)
{
  //根据孩子找父亲
  int parent = (child - 1) / 2;
  while (child > 0)
  {
    if (a[child] < a[parent])
    {
      HPDATAtype p = a[child];
      a[child] = a[parent];
      a[parent] = p;
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}
void Adjustdown1(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])
    {
      //交换
      int tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }else
    {
      break;
    }
  }
}
void heapsort1(int* a, int n)
{
  //向上调整建堆
  //从第一个元素开始就向上调整，保证前面都是堆结构,建小堆
  for (int i = 0; i < n; i++)
  {
    Adjustup1(a, i);
  }
  //在调整  ，选出一个个次小的数
  int end = n - 1;
  while (end > 0)
  {
    //把最小的数据交换到最后一个位置
    int tmp = a[0];
    a[0] = a[end];
    a[end] = tmp;
  Adjustdown1(a, end, 0);
  --end;
  }
}

建大堆------最后排序为升序


7fedda6da49a4ea0a0079600d2772937.png

void Adjustup2(HPDATAtype*a, int child)
{
  //根据孩子找父亲
  int parent = (child - 1) / 2;
  while (child>0)
  {
    if ( a[child]>a[parent])
    {
      HPDATAtype p = a[child];
      a [child] = a[parent];
      a[parent]=p;
      child = parent;
      parent = (child - 1) / 2;
    }
    else 
    {
      break;
    }
  }
}
void Adjustdown2(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])
    {
      //交换
      int tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void heapsort2(int* a, int n)
{
  //向上调整建堆
  //从第一个元素开始就向上调整，保证前面都是堆结构，建大堆
  for (int i = 0; i < n; i++)
  {
    Adjustup2(a, i);
  }
  //在调整  ，选出一个个次小的数
  int end = n - 1;
  while (end > 0)
  {
    //把最小的数据交换到最后一个位置
    int tmp = a[0];
    a[0] = a[end];
    a[end] = tmp;
    Adjustdown2(a, end, 0);
    --end;
  }
}

利用向上调整算法建堆，时间复杂度O(N*logN)，这里是以2为底N的对数。

2.向下调整建堆

建堆与向上调整建堆是相反的，向下调整建堆，从数组后面开始调整，也就是从二叉树后面开始从前调整，知道符合堆的特性。

向下调整建堆也分建大堆还是小堆，根据你设计向下调整算法时，取决于条件-孩子大与父亲还是父亲大于孩子。

这里建小堆，调整数组是下标从中间开始的。

建小堆--排序结果为降序

void Adjustdown1(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])
    {
      //交换
      int tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }else
    {
      break;
    }
  }
}
//向下调整建堆
void heapsort4(int* a, int n)
{
  HP f;
  Heapinit(&f);
  //向下调整建小堆
  //与向生调整建堆相反，这里是从数组后面开始调整堆，也就是从二叉树的下面开始
  for (int i =(n-1-1)/2 ; i >=0; i--)
  {
    Adjustdown1(a, n, i);
  }
  int end = n-1;
  while (end>0)
  {
    //进行排序
    int tmp = a[0];
    a[0] = a[end];
    a[end] = tmp;
    Adjustdown1(a, end, 0);
    --end;
  }
}

建大堆---排序结果为升序

void Adjustdown2(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])
    {
      //交换
      int tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void heapsort5(int* a, int n)
{
  HP f;
  Heapinit(&f);
  //向下调整建大堆
  //与向生调整建堆相反，这里是从数组后面开始调整堆，也就是从二叉树的下面开始
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    Adjustdown2(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    //进行排序
    int tmp = a[0];
    a[0] = a[end];
    a[end] = tmp;
    Adjustdown2(a, end, 0);
    --end;
  }
}

向上与向下比较

根据计算我们发现向下调整建堆是优于向上调整建堆的，这里的对于向下调整算法实现复杂度是O(N)，向上调整算法的时间复杂度为（N*logN）,应为向下调整算法，就如同在数组中插入，而向上调整算法经过错位相减或等比数列法计算大概为N*logN）。

文章标签：
算法
关键词：
数据结构应用
数据结构堆
数据结构堆应用
万众倾倒
目录
相关文章
恰小面包
|
17天前
|
存储 JavaScript 前端开发
什么是堆？什么是栈？他们之间从区别和联系
什么是堆？什么是栈？他们之间从区别和联系
恰小面包
31 0
终有链响
|
3天前
|
存储 NoSQL Redis
Redis数据结构精讲：选择与应用实战指南
Redis数据结构精讲：选择与应用实战指南
终有链响
13 0
toKeep
|
4天前
栈的基本应用
栈的基本应用
toKeep
11 3
warmhearted
|
5天前
|
存储 缓存 监控
中间件应用合理使用缓存和数据结构
【5月更文挑战第4天】中间件应用合理使用缓存和数据结构
warmhearted
19 3
中间件应用合理使用缓存和数据结构
风与烈酒
|
5天前
|
存储 程序员
什么是堆，什么是栈
什么是堆，什么是栈
风与烈酒
6 0
秦jh
|
8天前
【数据结构】二叉树-堆（top-k问题，堆排序，时间复杂度）
【数据结构】二叉树-堆（top-k问题，堆排序，时间复杂度）
秦jh
16 4
秦jh
|
8天前
【数据结构】二叉树-堆（函数实现）
【数据结构】二叉树-堆（函数实现）
秦jh
12 2
桃李春风一杯酒
|
10天前
|
存储 缓存 算法
【C 言专栏】C 语言中的数据结构应用
【5月更文挑战第4天】本文探讨了C语言中的核心数据结构，包括数组、链表（单链表和双链表）、栈、队列、二叉树（如二叉搜索树和二叉堆）以及图结构。这些数据结构在程序设计中扮演着关键角色，如数组的快速访问、链表的动态管理、栈和队列的处理流程控制、树和图的复杂关系表示。理解并选择适当的数据结构可优化程序性能，而内存管理和算法优化则进一步提升效率。通过案例分析和展望未来发展趋势，本文旨在帮助读者深化对C语言数据结构的理解和应用。
桃李春风一杯酒
29 4
【C 言专栏】C 语言中的数据结构应用
魏慧
|
14天前
|
存储 算法 Python
数据结构与算法基础及在计算机科学中的应用
数据结构与算法基础及在计算机科学中的应用
魏慧
16 0
皮牙子抓饭
|
15天前
|
存储 机器学习/深度学习 算法
数据结构算法入门指南：常见算法解析与应用
【4月更文挑战第28天】
皮牙子抓饭
9 0