【数据结构篇】探索堆的算法的巧妙
须知
💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！
👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对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 ( 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;
}
相信通过这篇文章你对堆排序的有了初步的了解。如果此篇文章对你学习数据结构有帮助，期待你的三连，你的支持就是我创作的动力！！！