什么网站可以做数据调查问卷,南京最新发布,上海交通大学文科建设处网站,腾讯云域名注册目录
#x1f31e;0.前言
#x1f688; 1.堆的概念
#x1f688; 2.堆的实现
#x1f69d;2.1堆向下调整算法
#x1f69d;2.2堆的创建#xff08;堆向下调整算法#xff09;
✈️2.2.1 向下调整建堆时间复杂度
#x1f69d;2.3堆向上调整算法
#x1f69d;2.… 目录
0.前言 1.堆的概念 2.堆的实现
2.1堆向下调整算法
2.2堆的创建堆向下调整算法
✈️2.2.1 向下调整建堆时间复杂度
2.3堆向上调整算法
2.4堆的创建堆向上调整算法
✈️2.4.1向上调整算法建堆的时间复杂度
2.5堆的插入
2.6堆的删除
2.7建堆的代码实现
✈️2.7.1向下调整实现堆的建立
✈️2.7.2向上调整实现堆的建立 3.完整的堆的代码的实现
3.1堆的创建
3.2堆的销毁
3.3堆的插入
3.4堆的删除头删
3.5取堆顶元素的数据
3.6 堆的数据个数
3.7堆的判空 4.堆的应用堆排序
✍5.结束语 0.前言 言C之言聊C之识以C会友共向远方。各位博友的各位你们好啊这里是持续分享数据结构知识的小赵同学今天要分享的数据结构知识是堆在这一章小赵将会向大家展开聊聊堆的相关知识。✊ 1.堆的概念 堆就是以 二叉树的顺序存储方式来存储元素同时又要满足 父亲结点存储数据都要大于等于儿子结点存储数据也可以是父亲结点数据都要小于等于儿子结点数据的一种数据结构。堆只有两种即大堆和小堆大堆就是父亲结点数据大于等于儿子结点数据小堆则反之。 同时这里要注意的是堆一定是完全二叉树不然就不是堆。那完全二叉树是什么呢这个地方不懂的博友可以看我们的这一篇博客数据结构C树的概念和二叉树初见http://t.csdnimg.cn/JnWfb
如果看完了还是不明白可以私信小赵询问哦。
好了下面让我们看看上面说的两种堆在图上是怎么呈现的呢 我们发现我们的任意一个父节点都比他的两个子节点大或等于这个时候这就是一个大堆。 我们发现我们的任意一个父节点都比他的两个子节点小或等于这个时候这就是一个小堆。
虽然堆是完全二叉树但其的存储方式却与二叉树不同我们一般存储堆的方式是数组。而我们上面所画的叫逻辑结构那怎么由数组的存储方式转化为我们的逻辑结构呢
我们在介绍二叉树的时候其实也曾简单的说过二叉树是有顺序的是从上到下从左向右的按这个顺序我们就可以给我们的二叉树标序号。 那么就可以我们的逻辑结构转化成我们的数组结构了既然我们已经会将逻辑结构转化为数组结构了那么将数组结构转化为逻辑结构也就没有这么难了大家可以自己试试如果实在实现不了也可以找小赵咨询哦。 2.堆的实现
2.1堆向下调整算法
什么是向下调整算法呢其实正如其名就是从上到下调整堆的意思。要想更深入了解这个东西就先来看这张图。 看这张图这是一个很明显的小堆对吧那我这个时候要你改成一个大堆怎么办这个时候的操作其实是23进行比较然后拿出大的和1换这个就成大堆了。 可如果这个时候我给你的是个这样的堆你又该怎么办要改成小堆 其实这个时候也是可以操作的因为下面是有序的堆我们只需要按照前面的顺序一步步来就可以完成了。只不过这个时候改成了选择两个子中的小的哪一个因为我们要做得是小堆这个时候之所以说他下面是有序的堆是因为盖住最上面的一个下面的两个堆都是小堆我们要改成的也是小堆。 那如果是无序的呢 改成小堆) 这个时候我们发现我们再想把这个改成小堆的难度就很大了。
2.2堆的创建堆向下调整算法
那通过上面的实验我们发现想通过一个位置来做上面的操作并把整个堆都变成小大堆必须下面就是一个小大堆。所以我们的向下调整其实也是从最下面的开始的而且我们刚刚做的步骤其实就是向下调整。
那么再面对上面那个无序的堆我们也就有方法了。 这个时候我们就可以做到将无序的堆转化成有序的堆了。 那么这个时候我们面对任何一个无序的数组都可以通过这样的方式将他转化成堆.至少在逻辑图上可以实现代码实现下面说
✈️2.2.1 向下调整建堆时间复杂度
每层节点个数 × 最坏情况向下调整次数 T(N) 2^(h-2) × 1 2^(h-3) × 2 … … 2^1 × (h-2)2^0*(h-1)
错位相减法 等号左右两边乘个 2 得到一个新公式再用新公式减去旧的公式具体见下图 2.3堆向上调整算法
聊了向下调整算法那么其实也有向上调整算法。
如这里我们如何把这个堆改成大堆 向上调整一般是怎么玩的呢一般我们的向上调整法就是从下面往上调整向这里要想调整到我们想要的样子就要三步 2.4堆的创建堆向上调整算法
这里呢也和上面一样向上调整的地方的上面必须是已经调整好的所以我们一般用向上调整法去建堆的时候往往要从第一个开始建堆到最下面。 ✈️2.4.1向上调整算法建堆的时间复杂度
T(N) 2^1× 1 2^2× 2 2^3 ×3 … … 2^(h-3)× (h-3) 2^(h-2) × (h-2) 2^(h-1) × (h-1) 综上向下调整建堆要更优秀效率更高 但总的来建堆的时间复杂度是O(N*logN)
2.5堆的插入
像我们一般堆是用数组存储的我们一般插入也是从数组后面插入所以也就是在最后一个位置插入而这个时候上面的堆都是有顺序的我们可以用我们的向上调整算法来解决堆的插入。 2.6堆的删除
堆的删除我们一般针对的是头元素的删除这个时候我们采取的策略是将头元素和尾元素交换然后让头元素向下调整因为下面的堆都已经是有顺序的 这样就可以完成头删了
2.7建堆的代码实现
代码的实现我们的表示表示方式和前面的双亲节点是对应的parent然后子节点就是child
✈️2.7.1向下调整实现堆的建立
//小堆的建立
void Swap(int* a, int* b)//交换
{int tmp *a;*a *b;*b tmp;
}
//小堆
void ADjustDown(int *a,int parent,int n)
{int child parent * 2 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 parent * 2 1;}else{break;}}
}
void Heap(int *a,int n)
{int i (n - 1 - 1) / 2;//找到最后一个双亲节点while (i 0){ADjustDown(a, i, n);i--;}
}
int main()
{int a[10] { 3,5,9,8,6,1,5,2,6,323 };Heap(a, 10);
}
这里的主要方式就是我们前面的图所演示的就是从最后一个双亲节点向下调整然后调整过程中要小心不要让字节出了数组的范围同时要记住子节点和双亲节点的关系。 这样可以方便我们的代码的实现。
✈️2.7.2向上调整实现堆的建立
//建立小堆
void Swap(int* a, int* b)//交换
{int tmp *a;*a *b;*b tmp;
}
void ADjustUp(int*a,int child,int n)
{int parent (child - 1) / 2;//双亲节点和子节点关系while (parent 0){if (a[child] a[parent])//如果子节点比双亲节点小那么交换并且向上移动{Swap(a[child], a[parent]);child parent;parent (child - 1 - 1) / 2;}else{break;}}
}
void Heap(int* a, int n)
{int i 0;while (i n)//从最上面开始建堆{ADjustUp(a, i, n);i;}
}
int main()
{int a[10] { 3,5,9,87,6,12,7,11,13,1 };Heap(a, 10);
}
这里也基本上就是我们上面逻辑的实现向上建堆就要保证上面都是已经建好的堆那么就得从首元素开始依次向下建堆。 3.完整的堆的代码的实现
要想实现完整的堆的实现就要实现以下几个函数
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
这样我们的堆就可以像之前的链表顺序表等一样使用了。
3.1堆的创建
和上面的代码逻辑基本一样。
这里我们主要采用的是向下排序建堆因为向下排序的时间复杂度低。
void HeapCreate(Heap* hp, HPDataType* a, int n)
{hp-_a (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp-_a NULL){perror(malloc failed);}memcpy(hp-_a, a, n);hp-_capacity n;hp-_size n;int i (n - 1 - 1) / 2;while (i 0){ADjustDown(a, i, n);i--;}
}
3.2堆的销毁
void HeapDestory(Heap* hp)
{free(hp-_a);hp-_a NULL;hp-_capacity 0;hp-_size 0;
}
3.3堆的插入
void HeapPush(Heap* hp, HPDataType x)
{if (hp-_size hp-_capacity){int newcapacity (hp-_size 0 ? 4 : hp-_capacity * 2);//如果没有内存就给4有就是原来内存的双倍HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(realloc failed);exit(-1);//退出程序返回-1}hp-_a tmp;hp-_capacity newcapacity;}hp-_a[hp-_size] x;hp-_size;ADjustUp(hp-_a, hp-_size - 1, hp-_size);//上面都是建好的堆只需要向上调整即可
}
3.4堆的删除头删
void HeapPop(Heap* hp)
{if (!HeapEmpty(hp)){Swap((hp-_a[0]), (hp-_a[hp-_size - 1]));//首尾交换ADjustDown(hp-_a, 0, hp-_size);//向下调整hp-_size--;//删除尾}else{return;}
}
3.5取堆顶元素的数据
HPDataType HeapTop(Heap* hp)
{if (HeapEmpty(hp))//不是空集返回首元素即堆顶元素{return hp-_a[0];}else{return NULL;}
}
3.6 堆的数据个数
int HeapSize(Heap* hp)
{return hp-_size;
}
3.7堆的判空
int HeapEmpty(Heap* hp)
{return hp-_size 0;//如果等式成立返回非零数不成立返回零
} 4.堆的应用堆排序
下面我们进入堆排序的学习堆排序是我们的排序中比较优的一个排序他具体是如何实现的呢其实我们在前面的知识中已经发现了就是如果我们建的是小堆那小堆的堆顶元素一定是整个堆里面最小的大堆的堆顶元素一定是最大的那么如果我们想排一个顺序的方法就出来了先把数组弄成一个大堆再把第一个元素和最后一个元素交换然后这个时候我们就排好了最大的一个接着我们不管最后一个元素对前面的n-1个元素再次建成大堆其实只要进行向下调整就可以了因为下面的已经是大堆了再重复上述操作。 那么我们就可以试着用代码实现了。
//建大堆
void ADjustDown(int* a, int parent, int n)
{int child parent * 2 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 parent * 2 1;}else{break;}}
}
void Heapsort(int* a, int n)
{int i (n - 1 - 1) / 2;while (i 0){ADjustDown(a, i, n);i--;}//建堆while (n 0){n--;Swap(a[0], a[n]);//交换首尾元素位置ADjustDown(a, 0, n);//下面都是建好的只要向下调整就可以}
}
int main()
{int a[10] { 3,5,9,87,6,12,7,11,13,1 };Heapsort(a,10);
}✍5.结束语
好了小赵今天的分享就到这里了如果大家有什么不明白的地方可以在小赵的下方留言哦同时如果小赵的博客中有什么地方不对也希望得到大家的指点谢谢各位家人们的支持。你们的支持是小赵创作的动力加油。 如果觉得文章对你有帮助的话还请点赞关注收藏支持小赵如有不足还请指点方便小赵及时改正感谢大家支持
文章转载自： http://www.morning.cflxx.cn.gov.cn.cflxx.cn http://www.morning.zzgtdz.cn.gov.cn.zzgtdz.cn http://www.morning.shangwenchao4.cn.gov.cn.shangwenchao4.cn http://www.morning.jpqmq.cn.gov.cn.jpqmq.cn http://www.morning.flpjy.cn.gov.cn.flpjy.cn http://www.morning.msbmp.cn.gov.cn.msbmp.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.yrblz.cn.gov.cn.yrblz.cn http://www.morning.qjldz.cn.gov.cn.qjldz.cn http://www.morning.gkxyy.cn.gov.cn.gkxyy.cn http://www.morning.kryn.cn.gov.cn.kryn.cn http://www.morning.zcnwg.cn.gov.cn.zcnwg.cn http://www.morning.cykqb.cn.gov.cn.cykqb.cn http://www.morning.tntbs.cn.gov.cn.tntbs.cn http://www.morning.iiunion.com.gov.cn.iiunion.com http://www.morning.nicetj.com.gov.cn.nicetj.com http://www.morning.gmysq.cn.gov.cn.gmysq.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.nllst.cn.gov.cn.nllst.cn http://www.morning.bqts.cn.gov.cn.bqts.cn http://www.morning.clzly.cn.gov.cn.clzly.cn http://www.morning.qyllw.cn.gov.cn.qyllw.cn http://www.morning.wwgpy.cn.gov.cn.wwgpy.cn http://www.morning.pqryw.cn.gov.cn.pqryw.cn http://www.morning.kgslc.cn.gov.cn.kgslc.cn http://www.morning.nhdmh.cn.gov.cn.nhdmh.cn http://www.morning.hxftm.cn.gov.cn.hxftm.cn http://www.morning.fdmfn.cn.gov.cn.fdmfn.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.pxwjp.cn.gov.cn.pxwjp.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.qbwtb.cn.gov.cn.qbwtb.cn http://www.morning.sjwzz.cn.gov.cn.sjwzz.cn http://www.morning.tmxtr.cn.gov.cn.tmxtr.cn http://www.morning.mjbnp.cn.gov.cn.mjbnp.cn http://www.morning.bqdpy.cn.gov.cn.bqdpy.cn http://www.morning.snrbl.cn.gov.cn.snrbl.cn http://www.morning.mnjwj.cn.gov.cn.mnjwj.cn http://www.morning.jppb.cn.gov.cn.jppb.cn http://www.morning.gctgc.cn.gov.cn.gctgc.cn http://www.morning.xckdn.cn.gov.cn.xckdn.cn http://www.morning.mltsc.cn.gov.cn.mltsc.cn http://www.morning.pltbd.cn.gov.cn.pltbd.cn http://www.morning.xkqjw.cn.gov.cn.xkqjw.cn http://www.morning.lqypx.cn.gov.cn.lqypx.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.chgmm.cn.gov.cn.chgmm.cn http://www.morning.lzzqz.cn.gov.cn.lzzqz.cn http://www.morning.tpxgm.cn.gov.cn.tpxgm.cn http://www.morning.drkk.cn.gov.cn.drkk.cn http://www.morning.wdlg.cn.gov.cn.wdlg.cn http://www.morning.wfdlz.cn.gov.cn.wfdlz.cn http://www.morning.rbgwj.cn.gov.cn.rbgwj.cn http://www.morning.yqwsd.cn.gov.cn.yqwsd.cn http://www.morning.nzhzt.cn.gov.cn.nzhzt.cn http://www.morning.tgtsg.cn.gov.cn.tgtsg.cn http://www.morning.lzwfg.cn.gov.cn.lzwfg.cn http://www.morning.cthkh.cn.gov.cn.cthkh.cn http://www.morning.jtcq.cn.gov.cn.jtcq.cn http://www.morning.yymlk.cn.gov.cn.yymlk.cn http://www.morning.mmhyx.cn.gov.cn.mmhyx.cn http://www.morning.cgntj.cn.gov.cn.cgntj.cn http://www.morning.sgbjh.cn.gov.cn.sgbjh.cn http://www.morning.gbfck.cn.gov.cn.gbfck.cn http://www.morning.nlrxh.cn.gov.cn.nlrxh.cn http://www.morning.iqcge.com.gov.cn.iqcge.com http://www.morning.hdnd.cn.gov.cn.hdnd.cn http://www.morning.mnjyf.cn.gov.cn.mnjyf.cn http://www.morning.drzkk.cn.gov.cn.drzkk.cn http://www.morning.lbqt.cn.gov.cn.lbqt.cn http://www.morning.yrhd.cn.gov.cn.yrhd.cn http://www.morning.xnbd.cn.gov.cn.xnbd.cn http://www.morning.rpwm.cn.gov.cn.rpwm.cn http://www.morning.qczjc.cn.gov.cn.qczjc.cn http://www.morning.zdwjg.cn.gov.cn.zdwjg.cn http://www.morning.wdlg.cn.gov.cn.wdlg.cn http://www.morning.xglgm.cn.gov.cn.xglgm.cn http://www.morning.jfjfk.cn.gov.cn.jfjfk.cn http://www.morning.pqkgb.cn.gov.cn.pqkgb.cn http://www.morning.pxbrg.cn.gov.cn.pxbrg.cn
