swap - その２。

Heap で用いる、Insert() 操作, Decrease_Key() 操作では、実際にデータを交換する事になるが、Extract_Min() 操作では、交換の必要がない。

通常ならば、Root (1) を取り出し、木構造を保持するために最後の値を持ってきてどこかによけておき、それ以外 (2 ~ 9) を１つ前に代入すればよい。こうすることで、書き込み回数はかなり削減（extract_min() 内では半分ほど）されると思う。


Heap の例では複雑なので、swap() するノードだけを抜粋している。
ex) 1 2 4 5 7 9

■今までの方法。
1 2 4 5 7 9
9 2 4 5 7
2 9 4 5 7
2 4 9 5 7
2 4 5 9 7
2 4 5 7 9


■今回の方法。
1 2 4 5 7 9
2 2 4 5 7 9
2 4 4 5 7 9
2 4 5 5 7 9
2 4 5 7 7 9
2 4 5 7 9