小程序商店多少钱,单页网站seo如何优化,昆山市建设局网站,咨询公司网站设计目录-笔记整理 一、思考二、堆概念与性质三、堆的构建、删除、添加1. 构建2. 删除3. 添加 四、复杂度分析4.1 时间复杂度4.2 空间复杂度 五、总结 一、思考
设计一种数据结构#xff0c;来存放整数#xff0c;要求三个接口#xff1a; 1#xff09;获取序列中的最值#… 目录-笔记整理 一、思考二、堆概念与性质三、堆的构建、删除、添加1. 构建2. 删除3. 添加 四、复杂度分析4.1 时间复杂度4.2 空间复杂度 五、总结 一、思考
设计一种数据结构来存放整数要求三个接口 1获取序列中的最值最大或最小 2添加元素 3删除最值最大或最小
分析
1如果使用无序的线性表来实现则需要发现获取最值、删除最值都需要遍历全部数据复杂度为O(n)
2如果使用有序的线性表则查找并删除最值是虽是O(1)级别但插入一个元素要重新进行排序最好情况也是O(n)
3如果平衡二叉查找树实现虽然查找、插入、删除复杂度是O(logsub2/subn)级别但其实现程度复杂功能多对于仅实现三个接口来说是”大炮打蚊子“得不尝失。而使用”堆“能很好实现三种接口且时间复杂度较低获取最大值O(1)添加、删除都为O(logsub2/subn)注这里的堆不是内存模型里的”堆空间“勿要混淆
二、堆概念与性质
堆(Heap)是一种数据结构物理存储采用顺序表其元素必须满足的性质是 { k i ≤ k 2 i 1 k i ≤ k 2 i 或 { k i ≥ k 2 i 1 k i ≥ k 2 i \lbrace^{k_i \leq k_{2i}}_{k_i \leq k_{2i1}} 或 \lbrace^{k_i \geq k_{2i}}_{k_i \geq k_{2i1}} {ki≤k2i1ki≤k2i或{ki≥k2i1ki≥k2i 我们称前者为小顶堆(或小根堆后者为大顶堆(或大根堆。观察发现这和完全二叉树的性质5很一样因此可以逻辑上理解堆为一棵完全二叉树。 例如序列5769810满足小根堆的性质 这棵完全二叉树的根元素又叫堆顶元素也是序列中的最小值因此每次查找最小值只需要获取堆顶元素即可添加一个元素后需要对堆重新进行调整每个元素满足堆性质成为一个新堆删除元素就是堆顶元素出堆然后重新调整元素位置直到全部元素满足堆性质成为一个新堆。
三、堆的构建、删除、添加
1. 构建
以小顶堆为例 如何使一个序列变成满足堆性质的序列并且具有添加、删除、获取最值三大接口需要思考两个问题 1如何由该混乱的序列构建一个堆 2往堆里添加、删除(删除堆顶元素后如何调整剩余元素成为一个新的堆
已知一个混乱序列1086975和一个空堆H然后遍历序列每遍历一个序列往空堆添加元素既要考虑每个元素满足堆的性质又要思考新添加的元素位置放在 i i i的位置还是 i 1 i1 i1的位置发现这种代码逻辑很难实现。由堆的性质和完全二叉树的性质类似把已知的混乱序列逻辑上形象的看成一个完全二叉树。那么问题就转化为如何把一个”混乱“的完全二叉树转变为一棵小根堆对于的完全二叉树
观察图发现我们只需要从非叶子 ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊n/2⌋结点开始以它为根对其根以及根的所有后代元素进行调整使其成为一棵小根堆直到 ⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor-1 ⌊n/2⌋−1 ~ 1 1 1位置为根元素都调整完毕构建堆完成。 如何调整 注假设现在有一个小根堆序列其对应的完全二叉树如上图所示 1堆顶元素输出或出堆让表尾元素11覆盖5并删除表尾元素 2根(11)和其左右孩子76中最小的比较发现6比11小则6和11交换位置这时以11为根的子树继续调整10比11小则互换位置…直到叶子结点若中途发现根比孩子中最小的还小则操作结束该棵子树已经调整好了 知道了如何调整那么堆的构建就是从非叶子 ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊n/2⌋结点为根的树进行调整直到 ⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor-1 ⌊n/2⌋−1 ~ 1 1 1位置为根的每棵树都调整一遍即堆构建完成
typedef int HeapType;
//构建堆传入一个无序序列和序列长度时间复杂度为O(n)
HeadType* CreateHeap(HeapType *H,int length){//由无序序列 H构建堆,该序列从索引0开始 int s;for(slength/2-1;s0;s--){//建立堆AdjustHeap(H,s,length);//调整函数}return H;
}//堆排序 ---O(nlogn)
void HeapSort(HeapType *H){int s;int top;//堆顶元素出堆表尾元素覆盖堆顶删除表尾元素即空出表尾单元原堆顶元素放在表尾for(slength;s1;s--){//进行length-1次出堆直到堆中只剩一个元素该元素的索引0topH[0];H[0]H[s-1];AdjustHeap(H,0,s-1);H[s-1]top;}
}2. 删除
堆中的删除操作就是删除堆顶元素其步骤和上文的如何调整一致其调整函数如下
void AdjustHeap(HeapType*H,int s,int len){ //slen/2-1//保存以索引s位置元素为根此时s位置的结点并不满足最小堆的性质其//他所有结点(s到len-1)位置的结点满足小顶堆的性质 int rcH[s];int i;for(i2*s1;ilen;i2*i1){//由完全二叉树的性质孩子结点和双亲结点的索引关系(注结点位置从索引0开始因此i2*s1而不是i2*s)if(ilen-1H[i]H[i1])i;//索引i是s孩子中的最小元素的索引if(rcH[i]) break;//若索引s处的元素小于孩子中最小的一个则调整结束H[s]H[i];si;}H[s]rc;
}3. 添加
往堆中添加元素就是先把新元素放在堆的末端再对新元素结点执行向上的操作即让其和双亲结点比较若新元素结点小于双亲结点则它们互换位置若互换后再于其双亲比较、交换直到整棵树的根结点索引为0的元素若中途遇到双亲小于新元素的则执行向上的操作结束添加完毕
void addElement(HeapType *H,HeapType e,int len){//注这里假设数组长度大(不会越界)len是元素的个数int newIndexlen;//新元素的索引int i(newIndex1)/2-1;//i是新元素的双亲的索引int eEleme;//暂存新元素for(i;i0;i(i-1)/2{//向上执行到根0号结点if(tElemH[i]){H[newIndex]H[i];newIndexi;}else{break; }}H[newIndex]eElem;
}四、复杂度分析
4.1 时间复杂度
创建堆是从非叶子结点 ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊n/2⌋位置的元素开始到根要调整的内部结点总数有 ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊n/2⌋这些结点分布在多个层次而构建堆过程中每次循环都要调用一次调整函数AdjustHeap()其每次执行调整函其中需要比较的次数和其结点所在的树中的层次到叶子结点的深度有关最坏的情况下。 推导过程如下 假设已知现在有目标堆是一个满堆即其对应结点总数为n2h-1的完全二叉树也是满二叉树深度为h根结点处于第1层。我们处于第h-1层的每个非叶子结点向下调整时最多比较一次第h-2层的最多比较2次…第一层的根结点则比较n-1次注这里没计入筛选孩子中最小值的那一次比较。第一层结点数21-11第二层结点数22-1…第h-1层的结点总数2h-2则总的比较次数S可能比较抽象如下表
树的层次结点数比较次数第1层1h-1第2层2h-2第3层22h-3………h-12h-21
则总的比较次数 S ( h − 1 ) 2 ∗ ( h − 2 ) 2 2 ∗ ( h − 3 ) . . . 2 h − 3 ∗ 2 2 h − 2 ∗ 1 2 h − h − 1 S(h-1)2*(h-2)2^2*(h-3)...2^{h-3}*22^{h-2}*12^h-h-1 S(h−1)2∗(h−2)22∗(h−3)...2h−3∗22h−2∗12h−h−1
又由于n 2h - 1即 hlog2(n1)则代入上式中Sn-h即创建堆时总比较次数S为O(n)级。往往堆排序过程中就包含建堆(O(n))和排序两个过程后者每输出一个堆顶元素则执行一次对根结点的调整(比较的次数规模O(h))即时间复杂度为O(log2n,综合为O(nlog2n)
4.2 空间复杂度
常数级O(1)
五、总结
堆排序在排序过程中使用常数个辅助单元其建堆时间为O(n)之后执行n-1次对当前的根向下的操作不管给定的初始序列是有序还是无序其用堆来排序的最好、最坏、平均时间复杂度均为O(nlog2n同时它是一种不稳定的排序虽然堆排序速度很快和快速排序时间复杂度一个水平但其速度却不如快速排序和时间复杂度的常数因子有关。快速排序虽然很快但是最坏的情况下时间复杂度达到O(n2空间复杂度达到O(n 注一般说某排序算法时间复杂度是多少通常指平均情况下的
