- 聚合分析
- 核算法
- 势能法
$\hat c_i - c_i = credit = \Phi (D_i)- \Phi (D_{i-1})$
$\sum \hat c_i = \sum c_i + \Phi(D-i) - \Phi(D_{i-1})$
合并两个skew heap摊还时间为O(logN)
Exercise
C
A light child has at most half weight of its parents. Thus if there are k light nodes not including x along the path from x to y, $w(y) \leq w(x)/2^k$ ( $k \leq log \frac{w(x)}{w(y)}$ )
$\Phi$ = the total number of right heavy nodes it contains
By lemma 2, any path in a skew heap contains only O(logn) light nodes
Any heavy node on such a path is converted from right to left by causing a drop of one in the potential
Two heaps $h_1$ and $h_2$, containing $n_1$ and $n_2$ items
$n = n_1 + n_2$
By lemma 1, the total number of light nodes is at most $2 \lfloor logn \rfloor -1$
Let $k_1$ and $k_2$ be the number of heavy nodes on the right path of $h_1$ and $h_2$, and $k_3$ be the number of nodes that become right heavy children of nodes on the merge path.
By lemma 2, $k_3 \leq \lfloor logn \rfloor$
the number of node on the merge path is at most
$c_i \leq 2+ \lfloor logn_1 \rfloor + k_1 + \lfloor logn_2 \rfloor + k_2 \leq 1 + 2 \lfloor logn \rfloor + k_1 + k_2$
The increase in the potential caused by the merge is $\Delta \Phi = k_3 - k_2 - k_1 = \lfloor logn \rfloor - k_1 - k_2$
This the amortized is at most $3 \lfloor logn \rfloor + 1$
Reference
https://blog.csdn.net/Woolseyyy/article/details/51517446