NOI导刊 基础数据结构-栈、队、堆

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,your family site,your site here,LOGO,NOIP,基础数据结构,江涛,队列、栈、堆概念与应用,目录,栈,队列,堆,3,数组,1,2,4,目录,数组,的,特性,数组,数组,(array),的元素,(element),或项,(item),的类型是相同的,数组的大小是固定的、静态的、连续的,数组对某元素的存取是,O(1),时间,数组的插入、删除操作是,O(n),时间,“订制”,数组,数组,由于数组通常的插入、删除操作是,O(n),时间的，在某些特定的条件下就显得低效了,.,因此我们通过对数组元素,操作的限制,，来达到,操作的高效,-,算法优化的突破点。,常见的,“,订制,”,数组有,:,栈、队列、堆等,.,它们操作的时间效率都很高。,注：虽然栈、队列、堆可以不用数组实现，但,NOIP,的实践中，用数组更简单实用。,栈,(stack),的图示,栈,栈的特性,栈,信息学中的栈一般就是用数组实现,栈,(stack),是后进先出,(last-in-first-out,LIFO),或先进后出,(FILO),的,栈有三个基本操作,压入,(push),弹出,(pop),取数,(getTop),操作都为,O(1),时间,栈有一个计数器,counter,或栈顶指针,栈的实现样例,Pascal,代码,栈,const,maxn=1000;,var,stack:,array,1.maxn of,integer,;,counter:,integer,;,Procedure,push(x:integer);,begin,/,入栈,inc(counter);stackcounter:=x;,end;,function,pop():integer;,begin,/,出栈,pop:=stackcounter;dec(counter);,end;,栈的实现样例,C+,代码,栈,const int,maxn=1000;,int,stackmaxn,counter=0;,void,push(,int,x),/,入栈,stack+counter=x;,int,pop(),/,出栈,return,stackcounter-;,栈的常见应用举例,栈,括号匹配,-,判断字符串,()(),是否括号匹配,运算表达式,-,计算表达式,3,*,(5-(2-3),*,(6+5)+8,*,5,回溯的非递归写法,凸包的,graham,扫描算法,队列,(queue),的图示,队列,队列的特性,队列,信息学中的队列一般也用数组实现,队列,(queue),是先进先出,(first-in-first-out,FIFO),或后进后出,(LILO),的,队列有三个基本操作,入队,(push),、,出队,(pop),、,取头,(getHead),操作都为,O(1),时间,队列有队头,front,和队尾,back,两个指针，一般也有个计数器,counter,const,maxn=1000;,var,queue:,array,1.maxn of,integer,;,front,back,counter:,integer,;,procedure,push(x:,integer,);,begin,inc(counter);inc(back);/,这样的话,front,back,初始化为,1,0,queueback:=x;,end;,function,pop():integer;,begin,pop:=queuefront;,inc(front);dec(counter);,end,;,队列的实现样例,Pascal,代码,队列,const,int,maxn=1000;,int,queuemaxn,counter=0,front=0,back=,-1,;,void,push(,int,x),queue+back=x;+counter;,int,pop(),-counter;,return,queuefront+;,队列的实现样例,C+,代码,队列,由于,front,和,back,一直向后移动，,有可能,counter,不大，但,back,却超过,maxn,，,而引起数组越界。,数组实现队列的可能缺点,队列,front,back,在保证,countermaxn then front:=1;,同样的，每次,back:=back+1;,后加上,if backmaxn then back:=1;,队列的,”,循环数组,”,方案,队列,队列的常见应用举例,队列,1,、宽度优先搜索（,BFS,）。,2,、单调队列：,a),有,n(n1000000),个数排成一行，找出一段长度为,L(1L=n),的连续一段，其中的最大值,a,与最小值,b,之差,(a-b),是最大,(,小）的。求这个最大值。,b),求,01,矩阵中最大的全零矩形,(,也可用栈做,),3,、,SPFA,算法,（循环数组队列）。,求,01,矩阵中最大的全零矩形,堆,(heap),的图示,堆,堆是以数组存储的,完全二叉树,，数组下标对应的节点关系如左图所示,如果每个节点的左、右节点的值都不比它的值小，则称为,小根堆,。反之，称为,大根堆,。,堆的特性,堆,堆,的本质,是,完全二叉树,只是用数组实现时编程简单、方便。,第,i,个节点的左孩子是第,2,*,i,个节点；右孩子是第,2,*,i+1,个节点。父节点,i div 2,n,个节点的堆，高度为,log,2,N.,堆有二个基本操作,增加一个元素,、,删除最值,都为,O(logN),时间。,取最值,为,O(1),时间。,const,maxn=1000;,var,heap:,array,1.maxn of,integer,;,counter:,integer,;,procedure add,(x:,integer,),；,/,增加一个元素值为,x,的过程,var,i:,integer,;,Begin,inc(counter);i:=counter;,heapi:=x;,while,(i1)and (heapi heapi,div,2),do,/,小根堆,begin,swap(heapi,heapi,div,2);i:=I,div,2;,end,;,end;,堆的实现样例,Pascal,代码,堆,procedure,down(i:,integer,),；,/,第,i,个元素被修改，维护堆过程,Begin,/,小根堆,while,(i,*,2=counter),do,begin,/,边界判断,i:=i,*,2;,if,(i+1heapi+1),then,i:=i+1;,if,heapiheap i,div,2,then,swap(heapi,heapi,div,2),else,break,;,end,;,end;,Procedure,del_min;,Begin,/,删除最小值（小根堆）,swap(heap1,heapcounter);,dec(counter);,down(1);,End,;,堆的实现样例,Pascal,代码,堆,堆的常见应用举例,堆,1,、堆排序。,2,、动态求最小,(,大,),值：,a),合并果子（,NOIP2004,提高组）,b),黑匣子,（见附录）,3,、,Dijkstra,算法的优化,(,类似的还有,Prim,算法,),。,求,01,矩阵中最大的全零矩形,附,1,(,黑匣子,),黑匣子,（全国青少年信息学奥林匹克联赛培训教材（中学高级本）,【试题描述】,我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量,i,。在初始时刻，黑匣子为空且,i,等于,0,。这个黑匣子执行一序列的命令。有两类命令：,ADD(x),：把元素,x,放入黑匣子；,GET,：,i,增,1,的同时，输出黑匣子内所有整数中第,i,小的数。牢记第,i,小的数是当黑匣子中的元素以非降序排序后位于第,i,位的元素,下面的表是一个,11,个命令的例子,附,1,(,黑匣子,),编,号,命令,i,黑匣子内容,输出,1,ADD(3),0,3,2,GET,1,3,3,3,ADD(1),1,1,3,4,GET,2,1,3,3,5,ADD(-4),2,-4,1,3,6,ADD(2),2,-4,1,2,3,7,ADD(8),2,-4,1,2,3,8,8,ADD(-1000),2,-1000,-4,1,2,3,8,9,GET,3,-1000,-4,1,2,3,8,1,10,GET,4,-1000,-4,1,2,3,8,2,11,ADD(2),4,-1000,-4,1,2,2,3,8,附,1,(,黑匣子,),现需要一个有效的算法处理给定的一系列命令。,ADD,和,GET,命令的总数至多有,3*104,个。定义,ADD,命令的个数为,M,个，,GET,命令的个数为,N,个。我们用下面的两个整数序列描述命令序列：,A(1),A(2),A(M),：加入黑匣子的元素序列。所有的数均为绝对值不超过,2*106,的整数。例如在上例中,A=(3,1,-4,2,8,-1000,2),。,u(1),u(2),u(N),：,u(i),表示第,i,个,GET,命令在第,u(i),个,ADD,命令之后，例如在上例中，,u=(1,2,6,6),。,你可以在假定自然数序列,u(1),u(2),u(N),以非降序排列，,N=M,，且对于每一个,p,（,1=p=N,）有,p=u(p)=M,。,【输入】,输入文件名为,blackbox.in,，其中第一行存放,M,和,N,的值，第二行存放,A(1),A(2),A(M),，第三行存放,u(1),u(2),u(N),。,【输出】,输出黑匣子的处理结果。,附,2,(job),工作安排,Richard Peng,2008,Farmer John,有太多的工作要做啊！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。,他的工作日从,0,时刻开始，有,1000000000,个单位时间（！）。在任一时刻，他都可以选择编号,1N,的,N(1=N=100000),项工作中的任意一项工作来完成。,因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有,N,个工作，虽然还是有可能。,对于第,i,个工作，有一个截止时间,D_i(1=D_i=1000000000),，如果他可以完成这个工作，那么他可以获利,P_i(1=P_i=1000000000).,附,2,(job),在给定的工作利润和截止时间下，,FJ,能够获得的利润最大为多少呢？答案可能会超过,32,位整型。,输入格式,第,1,行：一个整数,N.,第,2N+1,行：第,i+1,行有两个用空格分开的整数：,D_i,和,P_i.,样例输入,(job.in):,3,2 10,1 5,1 7,输出格式,:,输出一行，里面有一个整数，表示最大获利值。,样例输出,(job.out):,17,样例解释：,第,1,个单位时间完成第,3,个工作,(1,7),，然后在第,2,个单位时间完成第,1,个工作,(2,10),以达到最大利润,updata,