数据结构之树形结构2_堆课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,堆,数据结构之,树形结构,堆数据结构之树形结构,1,1.,什么是树？,复习,1.什么是树？复习,2,树,树,是由,n(n=0),个节点构成集合。特点是,任何两个节点间有且仅有一条路径,。,A,B,C,D,E,G,H,F,L,J,K,根节点,：没有父亲的节点。,一棵树只有一个根节点。,E,K,J,A,每个节点可有,0,个或多个儿子节点,除根节点外，每个结点,有且只有一个父亲,节点,J,和,K,是,E,的儿子节点E是J和K的父亲节点,A,是,E,的父节点,没有儿子的节点称为,叶节点,，比如,F,G,H,L,J,K,都是叶节点,父亲相同的节点称为,兄弟节点,，比如 F G H 是兄弟,节点的儿子的个数称为,节点的度,，比如 A 的度数为4,祖先、子孙,包含一个节点的所有子孙和该节点本身的集合，称为,子树,复习,树 树是由n(n=0)个节点构成集合。特点是任何,3,1.,什么是树？,2.,什么是二叉树？,复习,1.什么是树？2.什么是二叉树？复习,4,1.,什么是树？,2.,什么是二叉树？,3.,二叉树第,i,层最多有多少个节点？,复习,1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多,5,1.,什么是树？,2.,什么是二叉树？,3.,二叉树第,i,层最多有多少个节点？,4.,高度为,h,的二叉树最多有多少个节点？,复习,1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多,6,1.,什么是树？,2.,什么是二叉树？,3.,二叉树第,i,层最多有多少个节点？,4.,高度为,h,的二叉树最多有多少个节点？,5.,二叉树叶节点和度为,2,的节点的关系是？,复习,1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多,7,二叉树（Binary tree）,二叉树就是每个节点最多只有,两个子,节点的树。,二叉树的特点：,1.,第,i,层上最多有 个节点,2.,高度为,h,的二叉树最多有 个节点,2,i-1,2,h,-1,3.,在非空二叉树中，,叶节点的个数等于度为,2,的节点个数加,1,A,B,C,G,F,J,K,L,M,复习,二叉树（Binary tree）二叉树就是每个节点最多只有两,8,6.,什么是完全二叉树？什么是满二叉树？,复习,6.什么是完全二叉树？什么是满二叉树？复习,9,二叉树,每层节点数都达到最大的二叉树树叫,满二叉树,A,B,C,G,F,J,K,满二叉树,除最底层外，其余各层节点都达到最大值，且最底层的节点集中在,左侧,的连续位置上的二叉树叫,完全二叉树,。,A,B,C,G,F,K,完全二叉树,复习,二叉树每层节点数都达到最大的二叉树树叫满二叉树ABCGFJK,10,1,8,3,5,6,2,7,写出,前序,，,中序,，,后续,遍历序列,前顺：1,8,5,3,6,7,2,中序：8,5,1,7,6,2,3,后续：5,8,7,2,6,3,1,复习,1835627写出前序，中序，后续遍历序列前顺：1,8,5,11,二叉堆,(heap),二叉堆是完全二叉树,任何一个节点都大于他的儿子节点的值(大根堆),或者,任何一个节点都小于他的儿子节点的值(小根堆),父,子，则堆顶元素值一定最大,父1,）,/比如5号节点的父亲是2号节点,结点,heap,i,左孩子是,heap2*,i,，右孩子是,heap2*,i,+1,i,=n,/,2,根据堆的定义可以知道：,对于大根堆：,heap1,最大,heap,i,h2*,i,且,heap,i,heap2*,i,（,1,i,n,/,2,）,大根堆,heap,数组下标,堆用一维数组来存储，,父子关系可通过数组下标快速计算出来,#define Maxn 堆的最大元素个数 /#defi,13,已知下列数组表示一个堆，请画出这个堆！,12,38,27,72,66,49,45,下标,1 2 3 4 5 6 7 8,1,2,3,4,5,6,7,99,8,定理：堆的高度最大为,log,2,(n+1),因为高度为h的二叉树最多有2,h,-1个节点。,2,h,-1=n,那么h=log,2,(n+1),已知下列数组表示一个堆，请画出这个堆！12382772664,14,怎样建堆？,(小根),3,建堆开始,6,5,7,4,2,3,1,3,8,7,7,1,5,2,1,6,3,6,1,3,建堆完毕,数组heap,初始时,n=11 数组下标,从第下标为,n/2,的节点开始，,依次讨论下标为,n/2+1,n/2+2,.,2,1,建堆的时间复杂度为,O(n),详细证明见算法导论第77页，或者算法分析与设计第74页,数组heap,建堆完毕后,1,2,3,4,5,6,7,8,9,10,11,怎样建堆？(小根)3建堆开始65742313877152,15,堆的向下调整(小根),void,shift(,int,i,int n,),int,k,t;,t=heapi;,k=2*i;,while,(,k=,n,),if,(,(kheapk+1),),k+,;,if,(,theapk,),heapi=heapk;,i=k;k=2*i;,else,break;,heapi=t;,/,把以i号节点(下标为i)为根的,子树,调整为堆，n为堆最后一个节点的下标(也就是数组的长度),/k,表示当前节点孩子的下标,/,找出值最小的孩子的下标,/,把值最小的孩子的值赋值给根,/,结束循环,/,把根的值赋值交换给孩子,#define maxn 1000int,heap,max,n;,堆的向下调整(小根)void shift(int i,int,16,void,shift(,int,i,int n,),int,k,t;,t=heapi;,k=2*i;,while,(,k=,n,),if,(,(kheapk+1),),k+,;,if,(,theapk,),heapi=heapk;,i=k;k=2*i;,else,break;,heapi=t;,3,6,5,5,2,3,1,3,8,7,7,1,5,2,1,6,3,6,1,3,1,2,3,4,5,6,7,8,9,10,11,void shift(int i,int n),17,堆的向下调整(小根),void,shift(,int,i,int n,),int,k,t;,t=heapi;,k=2*i;,while,(,k=,n,),if,(,(kheapk+1),),k+,;,if,(,theapk,),heapi=heapk;,i=k;k=2*i;,else,break;,heapi=t;,/,把以i号节点(下标为i)为根的,子树,调整为堆，n为堆最后一个节点的下标(也就是数组的长度),/k,表示当前节点孩子的下标,/,找出值最小的孩子的下标,/,把值最小的孩子的值赋值给根,/,结束循环,/,把根的值赋值交换给孩子,#define maxn 1000int,heap,max,n;,建堆：,for,(,i=n,/,2,;i=,1,;i-,),shift(i,n);,调整一次堆的时间复杂度在最坏情况下是,O(log,2,n,),堆的向下调整(小根)void shift(int i,int,18,堆排序,堆排序的基础选择排序,堆排序的实质是利用二叉堆优化选择排序,堆排序步骤：,建堆。将所有节点布置成堆结构,取出堆顶节点,把堆尾的节点移动至顶部，调整此堆,跳转至2步骤，直至堆为空,堆排序堆排序的基础选择排序,19,堆排序,选择与维护,1,3,2,3,5,5,3,7,6,8,7,取出堆顶节点,7,1,2,7,3,7,2,8,8,3,3,8,6,8,一、取出,cout0),cout0)coutheap1,21,int,heap10,0,t,j,n;,void,shift(,int,i,int n,),int k,t;,t=heapi;,k=2*i;,while,(,k=,n),if,(,(kheapk+1),)k+;,if,(,theapk,),heapi=heapk;i=k;k=2*i,;,else,break,;,heapi=t;,int,main,(),cinn,;for,(,j=1,;j,heap,j;,for,(,j=n,/,2,;,j=,1,;j-),shift(j,n);,while(n0),coutheap1;,heap1=heap,n-,;,shift(1,n,);,return 0;,int heap100,t,j,n;int main(,22,例：NK宇宙班,题目描述：,CQNK中学高一年级总共有n(n=500000)个学生。现在你有他们的“星际语”成绩单，要从中找出“星际语”成绩最好的m(m=1000并且mn)个学生组成宇宙班，请按由高到低的顺序打印出加入于周班学生的“星际语”成绩。,输入格式：,第一行，两个整数n和m,第二行，n个用空格间隔的整数，分别表示n个学生的“星际语”成绩,输出格式：,只有一行，m个空格间隔的整数，表示加入宇宙班学生的“星际语”成绩。,样例输入：,12 5,89 87 77 95 68 56 100 80 65 95 99 71,样例输出：,100 99 95 95 89,例：NK宇宙班,23,直接对n个数由大到小排序，然后取最大的m个数取出来，,时间复杂度：,普通排序(冒泡、选择、插入)：O(n,2,+m),/一定超时,快速排序:O(nlog,2,n,+m),有没有更快的方法？,1.把n个数字建成堆,2.把堆顶节点的打印出来，删除堆顶元素，调整堆。,第2步重复m次。,O(n),O(log,2,n,),O(mlog,2,n,),总时间复杂度：O(n+mlog,2,n,),n最大为500000，2,19,=524288,也就是log,2,n,的值不超过19,直接对n个数由大到小排序，然后取最大的m个数取出来，有没有更,24,#define maxn 500001,using namespace std;,int heapmaxn,n,m;,void shift(int i,int len),/调整成大根堆,int t=heapi,k=2*i;,while(k=len),if(klen),/k记录值最大的孩子的编号,（大根堆）,if(theapk),heapi=heapk;,i=k;,k=2*i;,else break;,heapi=t;,int main(),int i;,scanf(%d%d,for(i=1;i=1;i-)shift(i,n);,/选出最大的m个数字,for(i=1;i=m;i+),printf(%d,heap1);,/打印堆顶元素的值，即取出最大元素,heap1=heapn;,/把最后一个节点移到堆顶，相当于把原来堆顶节点删了,n-;,/删除堆顶节点后，总节点数减1,shift(1,n);,/重新调整堆，把剩余节点中最大的值调到堆顶,return 0;,#define maxn 500001,25,堆的操作,堆的操作,26,/堆的向下调整,void,S,hift,Down,(int i,int,n,),int k,t;,t=heapi;k=2*i;,while(k=,n,),if(kheapk)heapi=heapk;i=k;k=2*i;else break;,heapi=t;,/堆的向下调整,27,/删除堆顶元素,void Del(),Heap1=Heapn;n-;,if(n0)ShiftDown(1,n);,/删除堆顶元素,28,/添加值为x的元素,void Insert(int x),n+;Heapn=x;,/将新元素添加在末尾,ShiftUp(n);,/向上调整堆,/添加值为x的元素,29,/堆的向,下,调整,void,S,hift,Down,(int,x,int,n,)/从编号为x的元素往,下,调整为小根堆,int k,t;,t=heap,x,;k=2*,x,;,while(k=,n,),if(kheapk)heap,x,=heapk;,x