因为对smooth sort所用到的资料结构有点兴趣，所以就拿来练习分析了，
有错欢迎鞭。
首先定义 L-tree 与 Leonardo Heap
L-tree 是一个二元树并满足以下性质：
1. order为 0 跟 1 的 L-tree 皆为一个节点
2. order为 m 的 L-tree 的左子树为 order m-1 的 L-tree，
右子树为 order m-2 的 L-tree
3. 若 order为 m 的 L-tree 用阵列表示，则其结构为
[ left subtree | right subtree | root ]
Leonardo Heap 是一组 L-trees 的集合并满足以下性质：
1. 所有的 L-tree 皆满足 minimum-heap property
2. 不存在重复 order 的 L-tree
3. 只能最小两个 order 的 L-tree 差是 1
4. 最小 order 的 L-tree 的 root 是 Leonardo Heap 的最小值
再来说明一下 Leonardo Heap 的操作
假设插入一个新元素 x ，则可以分两种情况：
1. 若最小 order 的 L-tree Ta 与次小 order 的 L-tree Tb 的 order 差 1
把 Ta 、 Tb 、 x 合成新的 L-tree Tc 进 Leonardo Heap ， Tc
需满足 minimum-heap property
2. 否则把 x 设为 size 1 的 L-tree 加进 Leonardo Heap
假设加入前的最小 order 的 L-tree 为 Ta
若 Ta 的 root < x ， 则交换两个 L-tree 的 root 并调整 Ta 使其
满足 minimum-heap property，反之不交换。
由此可知插入的时间复杂度为 O(log n)
关于 Leonardo Heap 的删除最小值：
假设最小 order 的 L-tree 为 Ta
1.a 若 Ta 的 size 为 1，则把 Ta 从 Leonardo Heap 移除
1.b 反之把 Ta 的 root 移除，使其分解成两个 L-tree 加入 Leonardo Heap 中
2. 假设在新的 Leonardo Heap 中，最小 order 的 L-tree 为 Ta'，
有最小root的 L-tree 为 Tb'。不失一般性，让 Ta' 不等于 Tb'。
则我们交换 Ta' 与 Tb' 的 root，并调整 Tb'使其满足
minimum-heap property
因此删除最小值的时间复杂度为 O(log n)
Amortized analysis
For given a Leonardo Heap H{i} = { L{k, i} | L{k, i} is the L-tree
with the k-th smallest order in i-th operation } in i-th operation
Let n{i} be the number of H{i}
h(L{k, i}) be height of L{k, i}
s(H{i}) be the number of L-tree in H{i}
Define a potential function phi(D{i}) for data structure state D{i}
1. phi(D{0}) = 0
2. phi(D{i}) = 0 if n{i} = 0
3. phi(D{i}) = sum { h(L{k, i}) } + h(L{1, i}) if n{i} > 0
The insertion analysis :
case 1 :
Let h(L{1, i - 1}) = t, h(L{2, i - 1}) = t + 1
ci = h(L{1, i - 1}) + 1
= t + 1
phi(D{i}) - phi(D{i - 1}) = ((t + 2) + (t + 2)) - ((t + 1) + t + t)
= 3 - t
ci' = ci + (phi(D{i}) - phi(D{i - 1}))
= (t + 1) + (3 - t)
= 4
case 2 :
Let h(L{1, i - 1}) = t
ci = h(L{1, i - 1}) + 1
= t + 1
phi(D{i}) - phi(D{i - 1}) = (t + 1 + 1) - (t + t)
= 2 - t
ci' = ci + (phi(D{i}) - phi(D{i - 1}))
= (t + 1) + (2 - t)
= 3
Hence, the insertion operation take O(1) amortized time.
The deletion analysis :
Let h(L{1, i - 1}) = t, h(L{2, i - 1}) = m
Assume W.L.O.G that second smallest element is the root of
L{x, i - 1} where x != 1
ci = h(L{x, i - 1}) + s(H{i}) + 1
Trivially, h(L{x, i - 1}) <= m1 * log(n{i})
s(H{i}) <= m2 * log(n{i})
for some constant m1, m2
So we know ci <= (m1 + m2 + 1) * log(n{i})
if t = 1, then
phi(D{i}) - phi(D{i - 1}) = (m + m) - (m + 1 + 1)
= m - 2
<= c1 * log(n{i})
for some constant c1
otherwise,
phi(D{i}) - phi(D{i - 1}) = ((t - 1) + (t - 2) + (t - 2)) - (t + t)
= t - 5
<= c2 * log(n{i})
for some constant c2
ci' = ci + phi(D{i}) - phi(D{i - 1})
<= (m1 + m2 + 1 + max{c1, c2}) * log(n{i})
Therefore, the deletion operation take O(log(n)) amortized time.
结论
Leonardo Heap 的插入 amortized time complexity 是 O(1)，然后删除
amortized time complexity 是 Θ(log n)
参考资料
https://en.wikipedia.org/wiki/Smoothsort