二叉堆、并查集和树状数组.doc

《二叉堆、并查集和树状数组.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、21二叉堆、并查集和树状数组优先队列•优先队列(priorityqueue):可以把元素加入到优先队列中,也可以从队列中取出优先级最高的元素,即以下ADT–Insert(T,x):把x加入优先队列中–DeleteMin(T,x):获取优先级最高的元素x,并把它从优先队列中删除堆的操作•用二叉堆(binaryheap)很容易实现优先队列•除了实现优先队列,堆还有其他用途,因此操作比优先队列多–Getmin(T,x):获得最小值–Delete(T,x):删除任意已知结点–DecreaseKey(T,x,p):把x的优先级降为p–Build

2、(T,x):把数组x建立成最小堆堆的定义•堆是一个完全二叉树–所有叶子在同一层或者两个连续层–最后一层的结点占据尽量左的位置•堆性质–为空,或者最小元素在根上–两棵子树也是堆存储方式•最小堆的元素保存在heap[1..hs]内–根在heap[1]–K的左儿子是2k,K的右儿子是2k+1,–K的父亲是[k/2]删除最小值元素•三步法–直接删除根–用最后一个元素代替根上元素–向下调整21•首先选取当前结点p的较大儿子.如果比p大,调整停止,否则交换p和儿子,继续调整voidsink(intp){intq=p<<1,a=heap[p];wh

3、ile(q<=hs){if(q=a)break;heap[p]=heap[q];p=q;q=p<<1;}heap[p]=a;}插入元素和向上调整•插入元素是先添加到末尾,再向上调整•向上调整:比较当前结点p和父亲,如果父亲比p小，停止;否则交换父亲和p,继续调整voidswim(intp){intq=p>>1,a=heap[p];while(q&&a>1;}heap[p]=a;}堆的建立•从下

4、往上逐层向下调整.所有的叶子无需调整,因此从hs/2开始.可用数学归纳法证明循环变量为i时,第i+1,i+2,…n均为最小堆的根voidinsert(inta){heap[++hs]=a;swim(hs);}intgetmin(){intr=heap[1];heap[1]=heap[hs--];sink(1);returnr;}intdecreaseKey(intp,inta){heap[p]=a;swim(p);}voidbuild()21{for(inti=hs/2;i>0;i--)sink(i);}时间复杂度分析•向上调整/向下

5、调整–每层是常数级别,共logn层,因此O(logn)•插入/删除–只调用一次向上或向下调整,因此都是O(logn)•建堆–高度为h的结点有n/2h+1个,总时间为例1.k路归并问题•把k个有序表合并成一个有序表.•元素共有n个.分析•每个表的元素都是从左到右移入新表•把每个表的当前元素放入二叉堆中,每次删除最小值并放入新表中,然后加入此序列的下一个元素•每次操作需要logk时间,因此总共需要nlogk的时间例2.序列和的前n小元素•给出两个长度为n的有序表A和B,在A和B中各任取一个,可以得到n2个和.求这些和最小的n个分析•可以把

6、这些和看成n个有序表:–A[1]+B[1]<=A[1]+B[2]<=A[1]+B[3]<=…–A[2]+B[1]<=A[2]+B[2]<=A[2]+B[3]<=…–…–A[n]+B[1]<=A[n]+B[2]<=A[n]+B[3]<=…•类似刚才的算法,每次O(logn),共取n次最小元素,共O(nlogn)例3.轮廓线•每一个建筑物用一个三元组表示(L,H,R),表示左边界,高度和右边界•轮廓线用X,Y,X,Y…这样的交替式表示•右图的轮廓线为:(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29

7、,0)•给N个建筑，求轮廓线21分析•算法一:用数组记录每一个元线段的高度–离散化,有n个元线段–每次插入可能影响n个元线段,O(n),共O(n2)–从左到右扫描元线段高度,得轮廓线•算法二：每个建筑的左右边界为事件点–把事件点排序,从左到右扫描–维护建筑物集合,事件点为线段的插入删除–需要求最高建筑物,用堆,共O(nlogn)例4.丑数•素因子都在集合{2,3,5,7}的数称为uglynumber•求第n大的丑数分析•初始：把1放入优先队列中•每次从优先队列中取出一个元素k，把2k,3k,5k,7k放入优先队列中•从2开始，取出的第

8、n个元素就是第n大丑数•每取出一个数，插入4个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn)•思考:如果集合元素个数m与n同阶,时间复杂度将变为怎样?如何优化?例5.赛车•有n辆赛车从各不相同的地方以各