算法导论——lec 12 平摊分析与优先队列

在平摊分析中，运行一系列数据结构操作所须要的时间是通过对运行的全部操作求平均得出。反映在不论什么情况下（即最坏情况下），每一个操作具有平均性能。掌握了平摊分析主要有三种方法，聚集分析、记账方法、势能方法。掌握了平摊分析的方法以后，我们就能够利用他来分析一些优先队列。

一、 平摊分析

【问题一】对作用于一个初始为空的栈上的n个PUSH、POP和MULTIPOP组成的序列进行分析。

【问题二】考虑一个由0開始向上计数的k位二进制计数器。

作用于一个初始为零的计数器上的n个INCREMENT操作的时间分析。

1、 定义： 在平摊分析中，运行一系列数据结构操作所须要的时间是通过对运行的全部操作求平均得出，反映在不论什么情况下（即最坏情况下）。每一个操作具有平均性能。

2、 特点： 即使某些单一的操作具有较大的代价。平均之后每一个操作的代价还可能是非常小的。平摊分析不牵扯到概率，适用于不论什么输入。所以能得到更精确的界值并设计更静止的数据结构。

3、 聚集分析： 用于确定一个n个操作序列的总代价的上界T(n)。每一个操作的代价能够表示为T(n)/n。我们把平均代价当做每一个操作的平摊代价，因此全部的操作具有同样的平摊代价。

a、 在平摊分析的聚集方法中，我们要证明对全部的n，n个操作构成的序列在最坏情况下总的时间为T(n)。

b、 在最坏情况下，每一个操作的平摊代价就为T(n)/n。

c、 这个平摊代价对每一个操作都是成立的，即使当序列中存在几种类型的操作时也是一样的。

注： 在记账和势能分析中不同操作的平摊代价可能不同。

【问题一分析】一个对象在每次被压入栈后至多被弹出一次。所以在一个空栈上调用POP(包括在MULTIPOP内的调用)的次数至多等于PUSH操作的次数。即至多为n。因此，对包括n个PUSH、POP和MULTIPOP操作序列的总时间为O(n)，每一个操作的平摊代价为O(n)/n = O(1)。

【问题二分析】在每次调用INCREMENT时，A[0]都要发生翻转，下一个高位A[1]每隔一次翻转：当作用与初始为零的计数器时，n次操作会导致A[1]翻转⌈n/2⌉次。类似地，位A[2] 每四次翻转一次，或在n次INCREMENT 中翻转⌈n/4⌉次。

一般地，对i = 0, 1, ..., k-1，在一个n 次INCREMENT操作的序列中，位A[i]要翻转⌈n/2^i⌉次，这个序列作用于初始为零的计数器上。对于i≥k，位A[i]始终不变。

因此，在序列中发生的位翻转的总次数为

最坏情况下，作用于一个初始为零的计数器上的n次INCREMENT操作的时间为O(n)。每次操作的平均代价为O(n)/n=O(1)。

4、 记账方法： 要确定每一个操作的平摊代价。当有一种以上的操作时。每种操作都可有一个不同的平摊代价。这样的方法对操作序列中的某些操作先“多记账”，将多记的部分作为对数据结构中的特定对象上“预付的存款”存起来。在该序列中稍后将用到这些存款。以补偿哪些对它们记的“帐”少于实际代价的操作。

我们对一个操作收费的数量称为其平摊代价。

假设希望通过对平摊代价的分析来说明每次操作的最坏情况平均代价较小，则操作序列的总的平摊代价必须是实际代价的一个上界，与在聚集分析中一样，这样的关系必须对全部的操作序列都成立。

a、 假设把第i个操作的实际代价用ci表示。第i个操作的平摊代价用c'i表示，对n个操作的全部序列我们须要：

b、 总存款：（对随意n都成立）

【问题一分析】我们对栈的操作赋予下面的平摊代价

PUSH
2

POP 0

MULTIPOP
0

此处全部三个平摊代价都是O(1)，如果用1元钱来表示代价的单位。開始时栈是空的。用餐厅中一堆迭放的盘子来类比栈数据结构。当把一个盘子压入栈时。我们用一元来支付压入动作的实际代价，还有1元存款，我们将其放在盘子顶上。因此在不论什么一个时间点，盘子上面都有一元存款。

盘子上的存款是用来预付将盘子从栈中弹出所需代价的。当运行了一个POP操作。对该操作不收取不论什么费用，仅仅要用盘中缩放的存款来支付代价就可以。对MULTIPOP操作也无需收取不论什么费用。

对随意的包括n次PUSH、POP和MULTIPOP操作的序列，总的平摊代价就是其总的实际代价的一个上界。由于总的平摊代价为O(n)，所以总的实际代价也是O(n)。

【问题二分析】我们规定把某一位置置1的操作收取2元的平摊费用。当某数位被置1后，我们用2元中的1元来支付置位操作的实际代价，而将另1元存在该位上作为余款。在不论什么时间，计数器中每一个1上都有1元余款，这样在将某位复位成0是不用付不论什么费。仅仅要取出1元余款就可以。由于计数器中为1的位数始终是非负的，因此余款永远是非负的。

对n次INCREMENT操作，总的平摊代价为O(n)。

5、 势能方法：与记账方法的相似之处在于要确定每一个操作的平摊代价，并且可能先对操作多记账以补偿以后的不足记账。

这样的方法将存款作为数据结构总体的“势能”来维护，而不是与数据结构中的单个对象联系起来。

势能方法開始时先对一个初始数据结构D0运行n个操作，对每一个i=1，2,3。...，n，设ci为第i次操作的实际代价，Di为对数据结构Di-1作用第i个操作的结果。势函数Φ将每一个数据结构Di映射为Φ(Di)，即与数据结构Di相关的势。

第i个操作的平摊代价为：

c‘i  = ci + Φ(Di) - Φ(Di-1)

从上式能够看出，每一个操作的 平摊代价为实际代价加上该操作所添加的势。N个操作的平摊代价：

假设我们定义一个势函数Φ使得Φ(Dn)>= Φ(D0)，则总的平摊代价就是总的实际代价的一个上界。

实际上，我们并不总是知道要运行多少操作，所以，假设要求对全部的i有Φ(Di)>= Φ(D0)。则就像记账方法中一样。我们保证预先支付。

通常为了方便，定义Φ(D0)=0。然后证明对全部的i，有Φ(Di)>=0。

从直觉上看。假设第i操作的势差Φ(Di)>= Φ(Di-1)是正的，则平摊代价表示对第i个操作多收了费。同一时候数据结构的势也添加了。假设势差是负值，则平摊代价就表示对第i个操作的不足收费，这是通过降低势来支付该操作的实际代价。

势函数Φ的增长为高代价操作做准备。

平摊代价由势函数决定。

【问题一分析】定义栈上的势函数为栈中对象的个数。開始为空栈， Φ(D0) = 0，栈中对象个数非负。即有  Φ(Di) >= 0 =  Φ(D0)。

Push操作作用于一个有s个对象的栈，则势差为 Φ(Di) -  Φ(Di-1) =
(s+1)-s = 1

那么，Push操作的代价为： c’i = ci + Φ(Di) -  Φ(Di-1) 
= 2

如果第i个操作是MultiPop(S, k)，且弹出了k’ = mim(k, s)个对象。该操作的实际代价为k‘，则

Φ(Di) - Φ(Di-1)= - k′

MULTIPOP操作的平摊代价为

ci + Φ(Di) - Φ(Di-1) =k’-k’=0

类似的。POP操作的平摊代价也是0.三种栈操作中每一种平摊代价都是O(1)，这样包括n个操作的序列的总平摊代价就是O(n)。

【问题二分析】我们定义在第i次INCREMENT操作后的计数器的势为bi 。即第i次操作后的计数器中1的个数。

我们来计算下一次INCREMENT操作的平摊代价。

如果第i次INCREMENT操作对ti 个位进行了复位。

该操作的实际代价至多为ti +1。由于除了将ti 个位复位外，它至多将1位置成1。所以，在第i次操作后计数器中1的个数为bi ≤ bi-1 - ti + 1，势差为

Φ(Di) - Φ(Di-1)≤ (bi-1 - ti + 1) - bi-1 =1 - ti

平摊代价为

ci + Φ(Di) - Φ(Di-1)≤ (ti + 1) + (1 - ti)=2

由于对于全部的i， Φ(Di)>= 0 ，故n次INCREMENT操作的序列的总平摊代价为总实际代价的一个上界。且n次INCREMENT操作的最坏代价为O(n)。

势能方法给我们一个简单的方法来分析计数器，即使它開始的时候不为0，開始的时候有b0个1， 此处0<=b0, bn<=k。我们有

故n次INCREMENT操作的实际代价为

由于b0 ，bn<=k，仅仅要k=O(n),总的实际代价就是O(n)。

换言之，假设我们运行了至少n=Ω(k)次INCREMENT操作，则不管计数器中包括什么样的初始值，总的实际代价都是O(n)。

二、 优先队列——二项堆

平摊分析多应用于分析复杂数据结构的基本操作的平摊代价。

优先级队列的基本操作：

a、 INSERT(S,x)：把元素x插入集合S；

b、 MAXIMUM(S)：返回S中具有最大keyword的元素；

c、 EXTRACT-MAX(S)：去掉并返回S中的具有最大keyword的元素。

d、 INCREASE-KEY(S,x,k)：将元素x的keyword的值添加到k，这里k值不能小于x的原keyword的值。

优先级队列 的应用： 最短路径、作业调度、分支定界。

【1】、 可合并堆的操作：

二叉堆在合并操作上是低效的，关键是要维护一个二叉树，为了使数据结构更为灵活，能够将二叉树变成森林。

Insert：将一个单节点的树增加森林。

Extract-Min：删除最小元素指针指向的元素，重置最小指针，可能须要树的重组。

Decrease-Key：将x剪下作为新的树，可能须要树的重组。

Union：合并两个森林的全部根，可能须要树的重组。

【2】、 Pairing Heap：仅在Extract-Min时进行树的重组。

1、 二项树

a、二项树的定义

B0：仅仅包括一个节点。

Bk：由两个Bk-1连接而成。当中一棵树的根是还有一棵树的根的最左孩子。

b、 二项树Bk的性质：

1）、 共同拥有2^k个节点。

2）、 树的高度为k。

3）、 在深度i处。恰有C(k, i)个节点。

4）、 根的度为k，它大于不论什么其它节点的度，而且假设根的子女从右往左编号：0,1,2,3,......,k-1，则相应的第i个子女就是子树Bi的根。

5）、 在一个包括n个节点的二项树中。随意节点的最大度数为lgn

2、 二项堆：二项堆H由一组满足例如以下二项堆性质的二项树组成：

a、 H中每一个树遵循最小堆性质：节点的keyword大于或等于其父节点的keyword——最小堆有序。

b、 对随意非负整数k，在H中至多有一棵二项树的根具有数k。

Note：由b可知。在n个节点的二项堆中，包括至多floor(lgn)+1棵二项树。

如图所看到的的二项堆：13个节点，3个二项树构成一个依照根的度数递增的链表。

更详细的表示：

3、 二项堆的操作：

a、 创建一个新的二项堆：

head[H] = NIL；

时间为O(1)

b、 寻找最小keyword：O(lg n)

Binomial-Heap-Minimum(H)
1 y<--nil
2 x<--head[H]
3 min<--INF
4 while x <> nil
5 do if key[x] < min
6 min<--key[x]
7 y<--x
8x<--sibling[x]
9 return y

c、 合并两个二项堆： O(lg n)

Binomial-Link(y, z)
1 p[y]<--z
2 sibling[u]<--child[z]
3 child[z]<--y
4 degree[z]<--degree[z]+1

以上操作的算法复杂度为O(1)。

Binomial-Heap-Union(H1, H2)
{
H<--Make-Binomial-Heap()
head[H]<--Binomial-Heap-Merge(H1, H2)
free H1 and H2 but not the list they point to
if head[H] = nil then return H
prev-x<--nil
x<--head[H]
next-x<--sibling[H]while next-x != x do
{
if(degree[x] != degree[next-x]) or (sibling[next-x] != nil and degree[sibling[next-x]] = degree[x]) then
{
prev-x<--x
x<--next-x
}else if(key[x] < key[next-x]){
sibling[x]<--sibling[next-x]
Binomial-Link(next-x, x)
}else{
if(prev-x = nil) then
head[H]<--next-x
else
sibling[prev-x] <-- next-x
Binomial-Link(x, next-x)
x<--next-x
}
next-x<--sibling[x]
}
return y
}

以上合并操作的算法复杂度为O(lg n)

d、 插入一个节点：O(lg n)

Binomial-Heap-Insert(H, x)
{
H'<--Make-Binomial-Heap()
p[x]<--nil
child[x]<--nil
sibling[x]<--nil
head[H']--x
H <-- Binomial-Heap-Union(H, H')
}

e、 抽取具有最小keyword的节点：O(lg n)

Binomial-Heap-Extract-Min(H)
{
find and remove the root with the min key in the root list of H
H' <-- Make-Binomial-Heap()
reverse the order of the linked list of x' s children and set head[H'] to point to the head of the resulting list
H <-- Binomial-Heap-Union(H, H')
return x
}

f、 减小keyword的值：O(lg n)

Binomial-Heap-Decrease-Key(H, x, k)
{
if k > key[x] then error "k>key[x]"
key[x]<--k
y<--x
z<--p[y]
while(z != nil and key[y] < key[z])
{
exchange key[y]<-->key[z] and other fields
y<--z
z<--p[y]
}
}

g、 删除一个keyword：O(lg n)

Binomial-Heap-Delete(H, x)
{
Binomial-Heap-Decrease-Key(H, x, -INF)
Binomial-Heap-Extract-Min(H)
}

三、 优先队列——斐波那契堆

1、 斐波那契堆的特点：

a、 与二项堆很相似。但不要求森林中的每棵树都是二项树。

b、假设没有DECREASE-KEY和DELETE，斐波那契堆里的每棵树都是二项树。

c、 仅仅有EXTRACT-MIN和DELETE的平摊代价是O(logn)。其它的都是Θ(1)。包含DECREASE-KEY，使得频繁用到DECREASE-KEY的图上算法在渐进分析上有飞跃！

2、 斐波那契堆是一组遵循最小堆性质的树。满足例如以下条件：

a、 树的根存放在双向链表中（H的根链表）；

b、 每棵树的根存放该树的最小元素；

c、 堆的最小值指针指向全部根中相应最小key值的那个。

d、对于每一个节点x，记录x的度数rank(x)，以及一个布尔变量mark(x)，记录其失去子女的情况。

说明：

a、 双向链表表示树根及孩子节点，这样从中删除节点以及合并两个节点都能够在常数时间完毕。

b、 树根列表是无序的。

c、 Mark规则：新生节点、节点成为还有一个节点的孩子时，设为false；失去一个孩子时设为true。

d、 定义势能函数：t(H)为堆中树的个数，m(H)是堆中被标记的节点的个数。

3、 斐波那契堆是由无序的二项树组成，而且无序二项树Uk具有下面性质：

a、 共同拥有2^k个节点；

b、 树的高度为k。

c、 在深度i处恰有C(k, i)个节点；

d、 根的度数为k。大于其它不论什么节点的度数；而且子女U0， U1。 ..Uk-1依照某种次序排列。

n个节点的无序二项堆的最大度数D(n) = lg n

4、 关键： Insert和Union的时候。不调整结构。这样可能导致树的个数增多，导致Extract-Min耗时。所以在Extract-Min调整结构。

5、 斐波那契堆的操作：

a、 插入节点：Fib-Heap-Insert，生成一个单一节点的树并插入root-list中。O(1)。

Fib-Heap-Insert(H, x)
1 degree[x]<--0
2 p[x]<--nil
3 child[x]<--nil
4 left[x]<--x
5 right[x]<--x
6 mark[x]<--false
7 将包括x的根表和根表H连接
8 if min[x] = nil or key[x] < key[min[H]]
9 then min[H]<--x
10n[H]<--n[H]+1

说明：1）新插入的树是原来min[H]的左兄弟；

2）不调整堆的结构，所以可能有度数同样的无序二项树；

3） 实际代价O(1)；

4） 平摊代价：O(1) + 1 = O(1)。

b、 合并堆：FIB-HEAP-UNION(H1, H2) 创建并返回一个包括堆H1和H2中全部节点的新堆。 O(1)。

Fib-Heap-Union(H1, H2)
1 H<--Make-Fib-Heap()
2 min[H]<--min[H1]
3 将H2的根表和H1的根表连接
4 if(min[H1] = nil) or (min[H2] != nill and min[H2] < min[H1])
5 then min[H]<--min[H2]
6 n[H]<--n[H1]+n[H2]
7 free H1 and H2
8 return H

说明：不调整堆的结构。势能变化是0，平摊代价等于实际代价O(1).

c、 抽取最小节点：Fib-Heap-Extract-Min(H)，抽取最小节点并调整结构。

Fib-Heap-Extract-Min(H)
1 z<--min[H]
2 if z != nil
3 then for each child x of z
4 do add x to the root list of H
5 p[x]<--nil
6 remove z from the root list of H
7 if z = right[z]//当右边节点为空的时候，right指针指向自己
8 then min[H]<--nil
9 else min[H]<--right[z]
10Consolidate(H)
11n[H]<--n[H]-1

说明： 下一步要调整H的根表。即降低斐波那契堆中树的数目，这由调用CONSOLIDATE(H)来完毕。对根表的调整过程即重复运行以下的步骤，直到根表中的每一个根都有一个不同的degree值。

过程CONSOLIDATE使用了一个辅助数组A[0..D(n[H])]，假设A[i]=y，则当前的y是个degree[y]=i的根。

1）.在根表中找出两个具有同样度数的根x和y。且key[x]≤key[y]

2）.将y与x链接：将y从根表中去掉，再使y成为x的一个孩子。这个操作由FIB-HEAP-LINK过程完毕。

域degree[x]被增值，且假设y上有标记的话也被去掉。

A[0..D(n[H])]：从当前min[H]指向的根開始，假设该度数的A[]为空，则填入；否则与A[]中记录的根链接。

下面是Consolidate的伪码：

Consolidata(H)
1 for i <-- 1 to D(n[H])
2 do A[i]<--nil
3 for each node w in the root list of H
4 do x<--w
5 d<--degree[w]
6 while A[d] != nil
7 do y<--A[d]
8 if key[x] > key[y]
9 then exchange x<-->y
10Fib-Heap-Link(H, y, x)
11A[d]<--nil
12d<--d+1
13A[d]<--x
14min[H]<--nil
15for i<--0 to D(n[H])
16do if A[i] != nil
17then add A[i] to the root list of H
18if min[H] = nil or key[A[i]] < key[min[H]]
19then min[H]<--A[i]

FIB-HEAP-LINK(H, y, x)：

1 从H的根表中去掉y

2 使y成为x的一个子结点，添加degree[x]

3 mark[y] ← FALSE

下面是Fib-Heap-Extract-Min的操作过程

说明：

1） 实际代价：由于在FIB-HEAP-EXTRACT-MIN中至多须要处理最小节点的D(n)个子女，除去CONSOLIDATEO(D(n))；在调用CONSOLIDATE时根的大小至多为D(n)+t(H)-1。

在6-12行的while循环的每一次运行中，有一个根要被链接到还有一个上，则for循环中所做的工作总量至多与D(n)+t(H)成正比，总的实际工作量为O(D(n)+t(H))。

2） 势能变化：在抽取最小节点之前的势为t(H)+2m(H)，而在此之后的势至多为(D(n)+1)+2m(H)，由于该操作之后至多留下D(n)+1个根，且操作中没有不论什么节点被加标记。

3） 平摊代价： O(D(n) + t(H)) + ((D(n) + 1) + 2 m(H)) - (t(H) + 2 m(H)) = O(D(n))

d、 减小一个keyword：减小keyword的时候会将关键词剪除，假设在一棵树根下CUT过多的话。可能是有问题的。因此引入Mark的概念。保证不在一个位置上过度CUT。

Fib-Heap-Decrease-Key(H, x, k)
1 if k > key[x]
2 then error "k > key[x]"
3 key[x]<--k
4 y<--p[x]
5 if y != nil and key[x] < key[y]
6 then Cut(H, x, y)
7 <span style="white-space:pre"></span>Cascading-Cut(H, y)
8 if key[x] < key[min[H]]
9 then min[H]<--x

CUT(H, x, y)
1 把x从y的子女表中删除。减小degree[y]
2 将x增加H的根表
3 p[x] ← NIL
4 mark[x] ← FALSE

Cascading-Cut(H, y)
1 z ← p[y]
2 if z ≠ NIL
3 then if mark[y] = FALSE
4 then mark[y] ← TRUE
5 else CUT(H, y, z)
6 Cascading-Cut(H, z)

说明： 1）先将46降低为15，再将35降低为5。此时Cascading-Cut发挥作用。由于Cut的节点的父节点Mark为true。所以父节点也要Cut。而父节点的父节点也Mark为True。所以也要被Cut。

能够这么觉得——每一个节点假设被剪除了两次子节点。那么这个节点也要被剪除，同一时候其父节点的 剪除次数也添加了一次。

      2） 实际代价： 假定在一次DECREASE-KEY的调用中要递归调用c次CASCADING-CUT。每次调用CASCADING-CUT的时间为O(1)。这样。 DECREASE-LEY的实际代价为O(c)。

3）势能变化： 对CASCADING-CUT的每次递归调用删除一个加了标记的节点并清除标记位。在此之后。共同拥有t(H)+c棵树(原来的t(H)棵树。由连锁删除产生的c-1棵树。以及以x为根的树)。和至多m(H)-c+2个加标记的节点(c-1)个节点被消除的标记，而最后一次调用CASCADING-CUT则可能给某一节点加上了标记。

)因此，势的改变最多为：((t(H) + c) + 2(m(H) - c + 2)) - (t(H) +
2m(H)) = 4 – c。

4） 平摊代价：O(c)+4-c=O(1)

没有Decrease-Key的话，D(n) = O(log n)；有的话，有些树不再是二项树，可是也差点儿相同。