【数据结构篇】探索堆的算法的巧妙

🕗 发布于 2024-11-06 18:00 数据结构 算法堆排序 Top-k问题向上调整算法时间复杂度

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

接上篇：【初阶数据结构】实现顺序结构二叉树-＞堆（附源码）-CSDN博客

上篇文章我们提及两个算法：向上调整算法和向下调整算法

哪个算法更高效？

1.向上调整算法时间复杂度

示例代码：

void AdjustUp(HPDataType* arr,int child)
{
int parent = (child - 1) / 2;
while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
{
if (arr[child] < arr[parent])
{
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}


void HPPush(HP* php, HPDataType x)
{
assert(php);
//判断空间是否足够
if (php->size == php->capacity)
{
//扩容
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newCapacity;
}
php->arr[php->size] = x;

AdjustUp(php->arr, php->size);

++php->size;
}

因为堆是完全⼆叉树，⽽满⼆叉树也是完全⼆叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本

来看的就是近似值，多⼏个结点不影响最终结果)

1.1 分析：

注：时间复杂度计算最坏情况下的次数,最差的情况就是堆中每个节点都要移动尽可能多的步数，可以得到下面计算公式：

则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）

上述使用错位相减求和。

根据大O渐进表示法得：

向上调整算法建堆时间复杂度为： O ( n ∗ log 2 n ) 即 O(nlogn)

2. 向下调整算法时间复杂度

堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后⼀个数据⼀换，然后删除数组最后⼀个数据，再进⾏向下调整算法。

步骤（如下图）：

示例代码：

void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
//while (parent < n)
while (child < n)
{
//找左右孩子中找最小的
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

注意：向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。

向下调整算法

• 将堆顶元素与堆中最后⼀个元素进⾏交换

• 删除堆中最后⼀个元素

• 将堆顶元素向下调整到满⾜堆特性为⽌

2.1 分析：

3. 堆的应用

优先级队列的使用场景：包括定时任务轮训问题、合并有序小文件

求Top K值问题【使用一个堆解决】求中位数、百分位数

大数据量日志统计搜索排行榜

3.1 堆排序

堆排序是一种利用堆这种数据结构设计的排序算法

3.1.1 排序一

使用现成数据结构->堆，将数据如堆，再取堆顶元素，在删除堆顶数据

// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
void HeapSort1(int* a, int n)
{
 HP hp;
    int arr1[6] = { 34,29,48,23,10,50 };
 for(int i = 0; i < 6; i++)
{
 HPPush(&hp,a[i]);
 }
     int i = 0;
     while (!HPEmpty(&hp))
     {
     a[i++] = HPTop(&hp);
     HPPop(&hp);
     }
      HPDestroy(&hp);
 }

使用麻烦，同时代码量还多，效率低，不建议使用。

3.1.2 排序二

比如排升序：建大堆，为啥？

依次将堆顶最大的数据与最后一个（不断发生变化）元素交换，每次都是将最大的数据放最后，可以想象一下，就是升序了。

// 升序，建⼤堆
// 降序，建⼩堆
// O(N*logN)
void HeapSort2(int* arr, int n)
{
int i = 0;
for ( i = 0; i < n; i++)
{
HPAdjustUp(arr, i);
}
int end = n - 1;
while (end)
{
Swap(&arr[0],&arr[end]);
HPAdjustDown(arr, 0, end);
end--;
}
}

时间复杂度：O（nlogn）

3.1.3 排序三

void HeapSort3(int* arr, int n)
{
for (int i =(n-1-1)/2 ; i >= 0; i--)
{
HPAdjustDown(arr, i, n);
}
int end = n - 1;
while (end)
{
Swap(&arr[0], &arr[end]);
HPAdjustDown(arr, 0, end);
end--;
}
}

建议使用向下调整算法建堆，原因：

移动多的步数节点少，移动少的步数节点多。

而向上调整算法：移动少的步数节点多，移动多的步数节点少。

显然少的步数少，次数就更少。

3.2 Top-k问题

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。

⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。

最佳的⽅式就是⽤堆来解决，基本思路如下：

⽤数据集合中前k个元素来建堆
前k个最⼤的元素，则建⼩堆；前k个最⼩的元素，则建⼤堆
⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素，然后再将交换进去后的元素向下调整（保证这k个元素始终是堆），最后将剩余N-k个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前k个最⼩或者最⼤的元素
代码如下:

void CreateNDate()
{
// 造数据
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand() + i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void TOPk()
{
int k = 0;
printf("请输入k:");
scanf("%d", &k);

const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail!");
exit(1);
}
int* minHeap = (int*)malloc(k * sizeof(int));
if (minHeap == NULL)
{
perror("malloc fail!");
exit(2);
}

//从文件中读取前K个数据
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}

//建堆---小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
HPAdjustDown(minHeap, i, k);
}

int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
//读取到的数据跟堆顶的数据进行比较
//比堆顶值大，交换入堆
if (x > minHeap[0])
{
minHeap[0] = x;
HPAdjustDown(minHeap, 0, k);
}
}

for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}

fclose(fout);
}

int main()
{
//CreateNDate();
TOPk();
return 0;
}

相信通过这篇文章你对堆排序的有了初步的了解。如果此篇文章对你学习数据结构有帮助，期待你的三连，你的支持就是我创作的动力！！！

原文地址：https://blog.csdn.net/braveact/article/details/143454784

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

linux-下载抖音作品
在linux中批量下载抖音作品。
阅读更多2024-11-06
基于Zynq FPGA对雷龙SD NAND的测试
进入测试程序前，首先会对SD卡初始化并初始化建立FATFS文件系统，随后进入测试SD卡测试程序，在测试程序中，会写入一定大小的文件，然后对写入文件的时间进行测量，得到写入时间；本来打算拿这些样片去试试
阅读更多2024-11-06
【综合案例】使用React编写B站评论案例
在文本框中输入要评论的文本，然后点击【发布】按钮，即可将评论添加到下方的评论列表当中进行展示；和普通JS变量不同的是，状态变量一旦发生变化组件的视图UI。classnames是一个简单的JS库，可以非
阅读更多2024-11-06
关于使用python pptx生成或“复制”PPT页面的问题
这里还要提一嘴PowerPoint，这里主要是不太熟悉这个，里面好多东西都不懂，加之我最开拿到的模板是不完善的，需要调整，然后出现了我当时认为奇葩的问题：有的母版可以删除，有的不可以，并且PPT页面删
阅读更多2024-11-06
Redis常见面试题（二）
Redis常见面试题（二）
阅读更多2024-11-06
基于 Python 的 Django 框架开发的电影推荐系统
Python、Django、Layui、requests、MySQL/SQLite3、数据分析、协同过滤算法、ECharts。
阅读更多2024-11-06
动态库实现lua网络请求GET, POST, 下载文件
编写lua动态库实现网络请求
阅读更多2024-11-06
【数据结构与算法】第8课—数据结构之二叉树(堆)
树是一种非线性的数据结构，它是由n(n>=0)个有限节点组成一个具有层次关系的集合，一般是树根朝上，树叶朝下树有一个特殊的节点，叫做根节点，根节点没有前驱节点树的根节点下面又有很多子节点，但是这
阅读更多2024-11-06
【论文复现】KAN卷积：医学图像分割新前沿
在医学领域，图像分割是一项至关重要的任务。它不仅能够帮助医生更准确地诊断疾病，还能在手术规划、治疗评估以及医学研究等多个方面发挥巨大作用。随着人工智能和深度学习技术的飞速发展，医学图像分割技术也迎来了
阅读更多2024-11-06
群控系统服务端开发模式-应用开发-本地上传工厂及阿里云上传工厂开发
群控系统服务端开发模式-应用开发-本地上传工厂及阿里云上传工厂开发
阅读更多2024-11-06