堆结构的两个应用
创始人
2024-06-03 11:11:45
0

堆排序

堆结构很大的一个用处,就是用于堆排序了,堆排序的时间复杂度是O(n∗log2n)O(n*log_2n)O(n∗log2​n)量级的,在众多排序算法中所处的地位也是高手级别的了。
但很多人在使用堆排序的时候,首先认为我必须得有一个堆数据结构才行,如下面代码这样:

//堆的结构定义
typedef int HDataType;
typedef struct Heap
{HDataType* a;//堆数据在物理上使用数组进行存储int size;//标记堆数据的有效个数int capacity;//标记堆空间的容量大小
}Hp;
Hp hp;//定义一个堆数据结构
HeapInit(&hp);//初始化堆int a[] = { 27,15,19,18,28,34,65,49,25,37 };
for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
{//为了进行堆排序,先将要排序的数据都push进堆数据结构中HeapPush(&hp, a[i]);
}
//此时,堆数据结构中存着一份要排序的数据,数组a里面存着一份要排序的数据int i = 0;
while (!HeapEmpty(&hp))
{//不断取堆顶元素,放进数组a中,当堆为空时,数组a就有序了a[i++] = HeapTop(&hp);HeapPop(&hp);
}
HeapDestroy(&hp);

这种堆排序方法也能排序,但未免有些不尽人意,没能充分利用堆的优势。
虽然时间复杂度达到了O(n∗log2n)O(n*log_2n)O(n∗log2​n),但额外的空间复杂度是O(n)O(n)O(n),因为需要先创建一个堆数据结构出来,用于存放要排序的数据。
如果是像C++的STL那样堆结构通过容器封装,可以直接拿来用的话还好说;但像C语言那样没有现成的堆数据结构可以用,那要想进行堆排序的话,还得自己先写一个堆数据结构出来,劳神费力,搞得复杂了。
所以,有没有什么更好的方法呢?
其实,细心观察不难发现,堆数据结构中的数据在物理上是使用数组进行存储的,而我们需要进行排序的数据也是存放在一个a数组中的,那我们是不是直接可以在a数组中进行堆排序了。
我们可以将a数组从逻辑上看成一棵完全二叉树,需要将其进行调整,以符合堆的结构。此时会涉及到堆的两种调整方式,这两种调整方式都能将一棵完全二叉树调整成堆结构:一个是向上调整建堆,一个是向下调整建堆。具体详情可参看阿顺的这篇博文堆的结构与实现。博文里面对于向上调整建堆和向下调整建堆都给出了时间复杂度的相应计算,最后发现,向下调整建堆的时间复杂度是O(n)O(n)O(n),向上调整建堆的时间复杂度是O(n∗log2n)O(n*log_2n)O(n∗log2​n),所以通过比较,我们自然会选择时间复杂度更优的那个,也就是向下调整建堆了。

//向下调整建堆:O(n)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(a, n, i);
}

此时,a数组已然从一棵完全二叉树蜕变成了一个堆结构。
好了,有了堆结构,如何在a数组上进行操作,将其变得有序呢?这似乎又是个难题。
细心的同学此时又发现,在阅读堆的结构与实现时看到,在介绍堆的向下调整时,首先说到了,堆的删除操作。在删除堆顶数据时,并不是像顺序表一样进行的是覆盖删除,而是用到了一种巧妙的交换操作。堆的删除操作与堆的向下调整天生不可分割 。沿着这个思路,是否能将这种交换操作延伸到堆排序中呢?
答案是肯定的。

//end等于数组数组最后一个元素的下标
int end = n - 1;
while (end > 0)
{//将堆顶数据和堆的最后一个数据进行交换Swap(&a[0], &a[end]);//end此时代表的是数组中的数据个数(n-1)个,将最后一个数据排除在外AdjustDown(a, end, 0);//end减一,end又成了最后一个要调整的数据的下标--end;
}

所以整个思想转换成代码如下:

void HeapSort(int* a, int n)
{//先向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}//O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
void HeapSortTest()
{int a[] = { 27,15,19,18,28,34,65,49,25,37 };HeapSort(a, sizeof(a) / sizeof(int));
}

要注意的是,通过以上思路分析,可以发现,要想排升序,需要建大堆,排降序,需要建小堆

Top-K问题

Top-K问题在实际生活中,还是很常见的。比如说:中国排名前10的大学,世界前500强企业,王者荣耀国服李白等等。
但很多时候,对于Top-K问题,能想到的最简单直接的方式就是排序了。结合问题所需是前K个最小的数据,还是前K个最大的数据,来决定是排升序还是排降序。但是,如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的处理方式还是用堆来解决。
根据上面对于堆排序的讲解,我们这里就可以很好的理解Top-K问题了。
有老铁说,我先用a数组中的前k个数据建个堆,再通过循环将前k个数据之后的数据,一个个都和堆顶数据进行比较,根据问题需求先进行替换,再进行堆的调整,最后这一折腾下来,堆中不就保留了我所想要的数据了吗。
但是,我想说的是,在了解上面的堆排序之后,我们能不能就在原地操作呢?
没错,我们就是要主观地认为,a数组中前k个数据就是我们想要的数据。先将前k个数据调整成堆,在通过循环将前k个数据之后的数据,一个个都和堆顶数据(a[0])进行比较,根据问题需求先进行替换,再进行堆顶数据的向下调整,最后循环完毕,a数组中的前k个数据也就是我们所需要的了。
根据思路,可以写出代码如下:

void TopKFind(int* a, int n, int k)
{assert(a != NULL);int* KMinHeap = a;//先将前k个数据调整成堆for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdjustDown(KMinHeap, k, i);}//将之后的数据与堆顶数据进行比较for (int i = k; i < n; ++i){//此处寻找的是前k个最大的数据if (KMinHeap[0] < a[i]){KMinHeap[0] = a[i];AdjustDown(KMinHeap, k, 0);}}
}

最后,需要注意的是,寻找前k个最小的数据,需要建大堆,寻找前k个最大的数据,需要建小堆。至于是要前k个最小的数据,还是前k个最大的数据,可以根据自己的需求,将判断条件略做更改即可。

相关内容

热门资讯

难忘的义工活动作文三年级【优... 难忘的义工活动作文三年级 篇一我参加的难忘的义工活动上个星期六,我参加了一次非常难忘的义工活动。这是...
三年级游泳级作文400字【优... 三年级游泳级作文400字 篇一我学会了游泳今天,我参加了学校游泳比赛,我非常开心,因为我终于学会了游...
三年级考试没考好的作文【最新... 三年级考试没考好的作文 篇一在三年级的学习生涯中,我曾经经历过一次考试没考好的经历。那是一次数学考试...
五颜六色的灯笼三年级优秀作文... 五颜六色的灯笼三年级优秀作文300字 篇一五颜六色的灯笼今天是中国传统的元宵节,我和爸爸妈妈一起来到...
三年级作文写风的颜色【优选6... 三年级作文写风的颜色 篇一风是一种无形的自然现象,但我们可以通过感受风的颜色来描绘它的特点。风的颜色...
两只小白兔小学三年级作文(优... 两只小白兔小学三年级作文 篇一我家养了两只小白兔,它们非常可爱。一只叫小白,另一只叫小米。它们的毛非...
三年级作文记一件难过的事作文... 三年级作文记一件难过的事作文400字19篇 篇一标题:失去宠物的痛苦今天,我要讲述一件让我非常难过的...
我有我的美丽700字作文三年... 我有我的美丽700字作文三年级 篇一我的美丽我觉得每个人都有自己的美丽,而我的美丽就是独一无二的。我...
我的学校150字作文三年级【... 我的学校150字作文三年级 篇一我所在的学校是一所小而美的学校。学校坐落在一个宁静的小镇上,周围环境...
小学三年级关于理想心愿的作文... 小学三年级关于理想心愿的作文 篇一我的理想心愿大家好!我是一名小学三年级的学生,今天我要和大家分享一...
三年级新乌鸦喝水作文【通用6... 三年级新乌鸦喝水作文 篇一新乌鸦是三年级的小动物,它非常聪明和好奇。有一天,它发现了一个水缸。水缸里...
天安门四季作文三年级(最新6... 天安门四季作文三年级 篇一天安门是中国的标志性建筑之一,它位于北京市中心,是人们敬仰和热爱的地方。天...
小学三年级作文400字(优质... 小学三年级作文400字 篇一:我的暑假生活暑假终于来临了,我迫不及待地开始了我的暑假生活。在这个暑假...
园一日游作文300字作文三年... 篇一:园一日游今天,我们三年级的同学们来到了一个美丽的园,进行了一次愉快的一日游。早晨,我们在学校门...
恐龙公园作文三年级【经典6篇... 恐龙公园作文三年级 篇一:探索恐龙世界在一个阳光明媚的周末,我和爸爸妈妈一起去了恐龙公园。我非常兴奋...
观察三年级的作文(实用6篇) 观察三年级的作文 篇一三年级的作文是一个让人感到充满惊喜和想象力的世界。作为一名老师,我有幸能够亲眼...
美丽的神农谷三年级作文(精简... 美丽的神农谷三年级作文 篇一神农谷是我家附近一个非常美丽的地方。每当我有时间,我都会去神农谷散步。神...
我的学校三年级作文(优质6篇... 我的学校三年级作文 篇一我喜爱的学校图书馆我所在的学校有一个很棒的图书馆,它是我最喜欢去的地方之一。...
三年级作文新学期的开始【经典... 三年级作文新学期的开始 篇一新学期的开始新学期开始了,同学们都充满了期待和憧憬。我们迈进了三年级的课...
小学三年级我的老师作文400... 篇一:小学三年级我的老师我非常喜欢我的小学三年级的老师,她是一个非常好的老师。她叫李老师,是一个年轻...