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

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

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

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

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

子の添字を k とすると：

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

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

class Heap

  def initialize
    @heap = []
  end

  def insert(x)
    @heap << x
    upheap
    self
  end

  def shift
    v = @heap.shift
    @heap.unshift(@heap.pop)
    downheap
    v
  end

  def upheap
    k = @heap.size - 1
    j = (k - 1) / 2    # parent of k
    until k == 0 || @heap[j] < @heap[k]
      @heap[j], @heap[k] = @heap[k], @heap[j]
      k = j
      j = (k - 1) / 2
    end
  end

  def downheap
    k = 0
    i = 2 * k + 1    # left child of k
    j = 2 * k + 2    # right child of k
    until @heap[i].nil?    # no children
      if @heap[j].nil? || @heap[i] < @heap[j]
        if @heap[k] < @heap[i]
          break
        else
          @heap[i], @heap[k] = @heap[k], @heap[i]
          k = i
          i = 2 * k + 1
          j = 2 * k + 2
        end
      else
        if @heap[k] < @heap[j]
          break
        else
          @heap[j], @heap[k] = @heap[k], @heap[j]
          k = j
          i = 2 * k + 1
          j = 2 * k + 2
        end
      end
    end
  end

end   # of class Heap

def heap_sort(ary)
  heap = Heap.new
  ary.each{|x| heap.insert(x) }
  result = []
  while y = heap.shift
    result << y
  end
  result
end

if $0 == __FILE__
  ary = (1..100).to_a.sample(10)
  puts "unsorted: " + ary.inspect
  result = heap_sort(ary)
  puts "sorted: " + result.inspect
end

実行例：

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

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