# 算法导论笔记0x15 —— 均摊分析 & 斐波那契堆

## 势能法 Potential Method

### Basic Knowledge

• 势能函数, Potential Function Φ : D → ℝ
• D is the set of states of the data structure.
• Di is state after i’th operation.
• ci is the cost of i’th operation.
• The amortized cost for i’th operation is $\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})$
• $\sum_i \hat{c_i}\geq \sum_i c_i$
• When we overcharge, i.e. $\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1}) > c_i$, Φ increases
• We “store” $\hat{c_i}-c_i$, which is called “credit” or “potential”
• When we undercharge, i.e. $\hat{c_i} < c_i$, Φ decreases
• We use stored credit to pay for $c_i – \hat{c_i}$
• Lemma Suppose Φ(Dn)≥Φ(D0). Then $\sum_{i=1}^n \hat{c_i}\geq \sum_{i=1}^n c_i$.
• To design Φ so that Φ(D0)=0 and Φ(Di)≥0 for all i.

### Binary Counter

• Consider a k-digit binary counter. When we increment the counter, we flip some bits.
• 每次比特翻转消耗1个单位。
• Φ(Di)=bi, where bi is the number of 1’s in Di.
• Suppose i’th operation sets ti bits from 1 to 0.
• Actual cost is ci = ti + 1
• Set ti bits from 1 to 0, and one bit from 0 to 1 for the carry(进位？)
• If bi = 0, the i’th operation reset all the bits.
• All bits were set in Di − 1
• ti = bi − 1 = k
• If bi > 0, then bi = bi − 1 − ti + 1.
• In both cases, bi ≤ bi − 1 − ti + 1
• Then Φ(Di)−Φ(Di − 1)=bi − bi − 1 ≤ 1 − ti
• $\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})\leq (t_i + 1) + (1-t_i) = 2$
• Φ(D0)=0, Φ(Dn)≥0
• $\sum_{i=1}^n c_i \leq \sum_{i=1}^n \hat{c_i} \leq 2n$

## 斐波那契堆

• Both Dijkstra’s and Prim’s algorithms take O((V + E)logV) time with a binary heap, and O(E + VlogV) time with a Fibonacci heap.
• Both algorithms decrease the key value heap items O(E) times.
• This takes O(ElogV) time on a binary heap, and O(E) time on a Fibonacci heap.
• 斐波那契堆比二叉堆复杂得多，在实际情况下通常不会表现得更好。
• 由多棵树的根节点连接而成
• 每棵树满足最小堆的性质 —— 即每个节点的值小于子孙节点
• 每个根节点被双向链表连接
• 每棵树的每个节点的子孙节点用双向链表连接
• 根节点中最小值的节点被 H.min 指向。
• 节点数存储在 H.n 中。
• 黑色的节点是被标记的marked.
• Marks are only used during decrease key and deletion operations.
• Suppose H has t(H) root nodes and m(H) marked nodes.
• The potential of H is Φ(H)=t(H)+2m(H)

### Basic Operations

• Let H and H’ denote the heap before and after an operation.
• Make-Heap
• Make an empty heap. Set H’.n=0, H’.min=NIL.
• Cost = O(1).
• Amortized cost = O(1), since Φ(H)=Φ(H′) = 0
• Insert a node
• Add the new node to the root list, left of the min node.
• Change H.min if new node’s key is smaller.
• Cost = O(1).
• Amortized cost = O(1).
• Number of roots increases by 1
• Φ(H′) − Φ(H)=(t(H)+4 + 2m(H)) − (t(H)+2m(H)) = O(1)

• Find the minimum
• Return H.min.
• Cost = amortized cost = O(1).
• Union of two heaps
• Concatenate the root lists of the two heaps H1 and H2.
• Set H.min to min(H1.min, H2.min)
• Cost = O(1)
• Φ(H′) − (Φ(H1)+Φ(H2)) = t(H′) + 2m(H′) − (t(H1)+2m(H1)+t(H1)+2m(H1)) = 0
• Amortized cost = O(1)

### Extract Min Node

• 移去 H.min 指向的节点
• 将每个 H.min 的子节点连带他们的子树移到根节点中
• The degree of a node is its number of children.
• We merge some of the trees in the root list, so that none of the roots have the same degree.
• The merging function is called CONSOLIDATE.
• Let D(H.n) be upper bound on the degree of any node in a Fibonacci heap with n nodes. D(H.n)=O(logn)
• Use an array A of size D(H.n)+1. A[i] points to a tree in the root list with degree i.
• 遍历根节点列表
• 如找到两个 degree 为 d 的根节点，我们连接(link)两个节点。
• A[d] = NIL, and A[d+1] = newly linked tree
• If 4 is marked, clear the mark.
• Finally, iterate through A array, and set H.min to the min root value.

Pseudocode for extract min

Complexity for extract min

• Real cost is O(D(n)+t(H))
• Potential befor extract min is at most t(H)+2m(H)
• Potential after extract is (D(n)+1)+2m(H)
• Amortized cost is
• O(D(n)+t(H)) + ((D(n)+1)+2m(H)) − (t(H)+2m(H)) = O(D(n)) + O(t(H)) − t(H)=O(D(n))
• we can scale up the units of the potential to cancel out the hidden constant in O(t(H)).

### Decreasing Key and Marking

• 减小一个节点的值，若与堆的性质不冲突则结束
• 若冲突，将被减小的节点移到根节点列表
• 如果父节点unmarked，将父节点mark
• 如果父节点marked，unmark父节点，将父节点移到根节点列表
• (unmark)若被unmark的节点的父节点被mark，对其父节点重复unmark & move to root list的操作
• A node is marked if one of its children has been cut, since the last time it’s been cut.
• One decrease key can create a sequence of cascading cuts.

• To delete a key, simply decrease its value to −∞ and then do a extract-min.
• Cutting a node: O(1)
• Decrease key operation creates c cascading cuts, then cost is O(c)
• For the amortized cost:
• After decrease key, the root list contains t(H)+c trees.
• It contains m(H)−c + 2 marked nodes.
• c-1 nodes were unmarked by cascading cuts, and the last call to CASCADING-CUT may have marked a node.
• Change in potential is (t(H)+c + 2(m(H)−c + 2)) − (t(H)+2m(H)) = 4 − c
• Amortized cost is O(c)+4 − c = O(1) by scaling the hidden constant in the potential appropriately.