二分ヒープ(ヒープ木)を使ったヒープソート

ヒープソートって配列を使ってやるのがフツウみたいだけど、アルゴリズムのアイデアに忠実に二分ヒープ(木)を使ってやってみた。
参考にしたページはココらへん。

 cf. 二分木 (binary tree) とヒープ (heap) – Algorithms with Python
 cf. 二分ヒープ – ウィキペディア

なんだかあんまりきれいじゃないけど。特に downheap のあたりが。
とりあえず出来たって感じ。
最初は upheap や downheap でノード自体を入れ替えようとしてたのでもっとひどかった。ノードはそのままにしておいて持っている値だけ入れ替えればいいことに気づいていくらかマシになった。

実行結果:

takatoh@nightschool $ ruby heap_sort.rb
unsorted: [75, 63, 96, 9, 21, 92, 48, 83, 51, 31]
sorted:   [9, 21, 31, 48, 51, 63, 75, 83, 92, 96]

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です