因為對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