😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏:数据结构
🔊本专栏主要更新的是数据结构部分知识点
💪种一棵树最好是十年前其次是现在
目录
0.利用堆的实现进行排序
1.堆排序
1.1 建堆
编辑
1.1.1 向上建堆
1.1.2 向下建堆
1.2 时间复杂度分析
1.3 堆排序
2.TopK问题
2.1 实现方法
2.2 实现过程
0.利用堆的实现进行排序
文章链接:【数据结构】堆的实现
在上篇博客里面,我们详细给出了堆的由来及其实现,其实由于堆这个结构的性质,也是可以直接对一个乱序数组实现排序的。不妨假设排升序并且有一个小根堆,实现过程如下:
- 首先,把数组里面的每个数都插入(HeapPush)到堆里。(注意HeapPush里面包含向上调整,所以每次插入之后都会保持堆这个结构)
- 其次,小根堆的堆顶是最小的,我们只需每次取出堆顶(HeapTop)元素到数组里面,从堆中取完之后,记得删除该元素(HeapPop)。由于HeapPop里面就有向下调整,每次删完之后都会保持堆的结构,也就是说堆顶元素永远都是最小的。接着一直重复上述操作,直至堆为空(HeapEmpty).
void HeapSort(int* a, int size)
{
HP hp;
HeapInit(&hp);
//把数组元素插入到堆里
for (int i = 0; i < size; i++)
{
HeapPush(&hp, a[i]);
}
int j = 0;
//依次遍历,取堆顶元素到数组,++下标,pop堆顶,依次循环
while (!HeapEmpty(&hp))
{
a[j] = HeapTop(&hp);
j++;
HeapPop(&hp);
}
HeapDestroy(&hp);//记得销毁
}
int main()
{
int a[] = { 3,4,1,9,6,7,5,8 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
很显然,每次要进行上述方法排序时都要手搓堆的实现代码,很繁琐!!!
1.堆排序
堆排序就是利用堆的思想来排序,总共分为两步:
1.建堆
2.利用堆删除思想来进行排序
1.1 建堆
关于建堆,有两种方法:
1.使用向上建堆,插入数据的思想建堆
2.使用向下调整建堆
1.1.1 向上建堆
图解过程:
代码如下:
#include <stdio.h>
#include <assert.h>
void AdjustUp(int* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])//小堆
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//升序
void HeapSort(int* a, int n)
{
//建堆
for (int i = 1; i < n; i++)//i从1开始遍历,因为第一个数据在堆里不需要调整,后续再插入时调整
{
AdjustUp(a, i);
}
}
int main()
{
int a[] = { 3,4,1,9,6,7,5,8 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d ", a[i]);
}
return 0;
}
运行结果:
1.1.2 向下建堆
首先不能直接进行向下调整,因为向下调整的前提是 必须保证根结点的左右子树均为小堆,但是这里的数组是乱序的,因此不能直接使用。但是我们可以 从倒数第一个非叶结点开始向下调整,从下往上调。这又出现了一个问题,那就是倒数第一个非叶结点在哪呢,通过画逻辑图不难看出,其实 最后一个结点的父亲就是倒数第一个非叶结点。当我们找到这个非叶结点时,把它和它的孩子看作一个整体,进行向下调整。调整之后,再将次父结点向前挪动,再次进行向下调整,依次循环下去。
图解过程:
#include <stdio.h>
#include <assert.h>
void Swap(int* pa, int* pb)
{
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void AdjustUp(int* a, int child)
{
assert(a);
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;
}
}
}
void AdjustDown(int* a, int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//升序
void HeapSort(int* a, int n)
{
建堆
//for (int i = 1; i < n; i++)//i从1开始遍历,因为第一个数据在堆里不需要调整,后续再插入时调整
//{
// AdjustUp(a, i);
//}
//建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
}
int main()
{
int a[] = { 3,4,1,9,6,7,5,8 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d ", a[i]);
}
return 0;
}
运行结果:
满足小堆性质。
1.2 时间复杂度分析
1.1中的向上建堆和向下建堆哪个时间复杂度更小呢?
综上所得,向下建堆时间复杂度更低。即使我们不用公式去推,我们也可以直观感受到二叉树越往下的结点就越多,下面结点越多向下建堆的次数就越少,而向上建堆相反,下面越多反而向上建堆的次数就越多。相比之下,向上建堆的复杂度明显高于向下建堆。
1.3 堆排序
在进行堆排序之前要思考一个问题——升序降序分别应该建什么堆?
解:假设升序建小堆,有了上述时间复杂度的分析,我们采用复杂度较低的向下建堆,并且建好堆之后,堆顶元素必然是最小的一个。如果继续使用小堆的话,从第二个数开始往后当作堆,此时堆这个结构全乱了。反之,如果采用大堆的话,就会方便很多。因此升序要建大堆。
下面进入堆排序正文部分:
1.先建好大堆:
2.核心操作:我们把第一个数和最后一个数互换位置,并且最后一个数直接丢掉,即数组下标减减。此时左右子树仍是大堆,就可以再次进行向下调整。
图解过程(注:因为是最后一个元素不看做堆里的部分,因此是倒序确定)
代码如下:
#include <stdio.h> #include <assert.h> void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } void AdjustDown(int* a, int n, int parent) { int child = 2 * parent + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { ++child; } if (a[child] > a[parent])//大堆 { Swap(&a[child], &a[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } //升序 void HeapSort(int* a, int n) { //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //大堆升序 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } } int main() { int a[] = { 3,4,1,9,6,7,5,8 }; HeapSort(a, sizeof(a) / sizeof(int)); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { printf("%d ", a[i]); } return 0; }
输出结果:
2.TopK问题
TopK问题,顾名思义就是N个数里面找出最大/最小的前k个。通常适用于数据比较大的情况。
这里我们不妨取在10000个数里面找出最大的前10个。
2.1 实现方法
对于TopK问题,通常会有以下几种方法:
1.排序:先排降序(快排),前10个就是最大的。
2.将N个数依次插入大堆,再pop个k次,每次取出栈顶元素。
相较于法一,法二似乎更优,然而这也引发了一些问题:如果N非常大,以至于远远大于k。此时法一法二就不能在用了,因为此时会导致内存不足。因此就有了法三的由来:文章来源:https://www.toymoban.com/news/detail-429252.html
3. 用前k个数建立一个k个数的小堆,然后让剩下的N-K个依次遍历,如果比堆顶的数据大,就替换它进堆(向下调整),最后堆里面剩下的就是最大的前k个。
2.2 实现过程
test.c文章来源地址https://www.toymoban.com/news/detail-429252.html
// 向下调整
void AdjustDown(int* a, int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
//选出左右孩子中小的那个
if (a[child + 1] < a[child])
{
++child;
}
//如果小的孩子小于父亲,则交换,并继续向下调整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void PrintTopK(int* a, int n, int k)
{
// 1. 建堆--用a中前k个元素建堆
int* minHeap = (int*)malloc(sizeof(int) * k);
assert(minHeap);
for (int i = 0; i < k; i++)
{
minHeap[i] = a[i];
}
// 2. 建小堆
for (int j = (k - 1 - 1) / 2; j >= 0; j--)
{
//从倒数第一个非叶结点开始
AdjustDown(a, k, j);
}
// 3. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
for (int i = k; i < n; i++)
{
if (a[i] > minHeap[0])
{
minHeap[0] = a[i];//如果比堆顶大就替换他
AdjustDown(minHeap, k, 0);// 向下调整确保为堆
}
}
for (int j = 0; j < k; j++)
{
printf("%d ", minHeap[j]);//打印
}
printf("\n");
free(minHeap);//销毁
}
void TestTopk()
{
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
srand(time(0));
for (int i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;//生成一个随机数,使其数值都小于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;
}
到了这里,关于【数据结构】堆排序和TOPK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!