堆结构的两个应用
创始人
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个最大的数据,可以根据自己的需求,将判断条件略做更改即可。

相关内容

热门资讯

我的札记本作文(精简5篇) 我的札记本作文 篇一我的札记本是我生活中的得力助手。它陪伴我度过了许多美好的时光,记录了许多珍贵的回...
鸡年春节歌曲:迎春花歌词(精... 鸡年春节歌曲:迎春花歌词 篇一《迎春花》是一首充满喜庆和欢乐气氛的鸡年春节歌曲。这首歌曲以迎春花为主...
少年的模样-记叙文【精彩5篇... 少年的模样-记叙文 篇一夏日的阳光透过窗帘洒在地板上,照亮了少年的脸庞。他身穿一件白色的T恤,牛仔裤...
初中英语作文:蘑菇 Mush... 初中英语作文:蘑菇 Mushrooms 篇一Mushrooms are a type of fung...
遇见作文【通用6篇】 遇见作文 篇一近年来,作文成为了学生们备受关注的一项重要考试内容。然而,对于很多学生来说,作文却是一...
游藏龙百瀑初一作文【优选6篇... 游藏龙百瀑初一作文 篇一游藏龙百瀑初一作文 篇一游藏龙是我国著名的风景名胜区之一,位于贵州省黔东南苗...
初中的军训作文600字(精选... 初中的军训作文600字 篇一初中的军训是一次难忘的经历初中的军训是每个初中生都会经历的一段时光。我记...
我的未来我做主初一作文(精选... 我的未来我做主初一作文 篇一我的未来我做主未来,是一个充满无限可能的词汇。在这个时代,我们都有自己的...
同上一堂课雷锋告诉我作文(通... 篇一:同上一堂课雷锋告诉我雷锋是一位伟大的人物,他的事迹深深地感动了我。上一堂课,我们学习了雷锋的故...
水仙初一作文(优质5篇) 水仙初一作文 篇一我的初一生活初一,是一个全新的开始,也是我人生中的一个重要阶段。我迎来了初中生活,...
从前的我们的作文500字【优... 从前的我们的作文500字 篇一过去的我们总是无忧无虑地生活着,那是我们最纯真的时光。回想起那些年,我...
我庆幸我是中国人初一作文55... 我庆幸我是中国人初一作文550字 篇一作为一个初一学生,我庆幸自己是中国人。中国是一个拥有五千年文明...
初中作文题材万能素材积累【精... 初中作文题材万能素材积累 篇一 随着社会的发展,人们对于环境保护的意识越来越强烈。环境污染已经成为...
亲切的怀恋作文(优选3篇) 亲切的怀恋作文 篇一怀恋已逝的时光记忆是一扇扇窗户,打开时可以穿越时光,回到过去。尽管时间已经过去了...
我真开心初一范文63篇 我真开心初一范文 第一篇我相信大家对于那些能够让自己开心快乐的事情肯定不会淡忘。在去年的时候,尤其是...
天堂寨之行初一作文(优质3篇... 天堂寨之行初一作文 篇一天堂寨之行初一暑假,我和家人一起来到了著名的旅游景点——天堂寨。这是一个位于...
消失在记忆里的光阴初中作文8... 消失在记忆里的光阴初中作文800字 篇一初中时光如流水般消失在我的记忆里,仿佛昨日的事情转眼间已经过...
难忘的一件事作文初一600字... 难忘的一件事作文初一600字 篇一我难以忘怀的一件事发生在我小学五年级的时候。那是一个晴朗的春天,阳...
初中散文:人间有真情(精选5... 初中散文:人间有真情 篇一人间有真情人间有真情,是一种温暖的存在。我还记得那个夏天,当我意外受伤时,...
在回家的路上初中作文【经典5... 在回家的路上初中作文 篇一回家是每天都要经历的事情,也是我最期待的时刻。每天放学后,我都会急匆匆地赶...