配列を使ったヒープソート

一昨日は二分木を使ったヒープソートを作った。配列を使ったヒープの構造についてはここのページのヒープの項が分かりやすい。

 cf. 二分木 (binary tree) とヒープ (heap) – Algorithms with Python

二分木のルートを番号 0 として、各ノードに幅優先で左から番号をふっていく。ふった番号を配列の添字だと考えれば、次の関係が成り立つ。
すなわち、親の添字を k とすると:

  • 左側の子の添字は 2 * k + 1
  • 右側の子の添字は 2 * k + 2

子の添字を k とすると:

  • 親の添字は floor((k – 1) / 2)

となる。
これで二分木を配列に置き換えられる。後はやることは基本的に一緒だ。

実行例:

unsorted: [15, 70, 93, 27, 5, 8, 26, 40, 74, 67]
sorted:   [5, 8, 15, 26, 27, 40, 67, 70, 74, 93]

[おまけ]

二分木を使ったヒープソート(heap_sort.rb)と今日の配列を使ったヒープソート(heap_sort2.rb)の実行時間の比較をしてみた。

takatoh@nightschool $ time ruby heap_sort.rb
unsorted: [85, 61, 68, 9, 73, 79, 26, 84, 21, 13]
sorted:   [9, 13, 21, 26, 61, 68, 73, 79, 84, 85]

real	0m0.102s
user	0m0.019s
sys	0m0.008s
takatoh@nightschool $ time ruby heap_sort2.rb
unsorted: [65, 26, 92, 51, 33, 31, 61, 97, 34, 57]
sorted:   [26, 31, 33, 34, 51, 57, 61, 65, 92, 97]

real	0m0.034s
user	0m0.017s
sys	0m0.017s

配列を使ったヒープソートのほうが3倍位速い。ま、そうだろうな…と思ったら、user の時間は大して変わらないな。

コメントを残す

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