heapsort

データ構造の説明

• ひとつの配列でヒープを表している(classを作って再帰的にとかしてない）
• a[0..(a.size-1>>1)]までが親
• a[i*2+1]が左側の子
• a[i*2+2]が右側の子
• 常に親＞子の関係が成り立っている。

a=(0..30).map{rand(100)}

def a.heapsort &block
  n = self.size-1
  #全体をヒープに組み上げる
  (n>>1).downto(0){|i| heaplify i, n}

  block.call(self) if block #ヒープの形を表示するためのフック

  #ヒープを元にソートする
  n.downto(0) do |last_idx|
    swap 0, last_idx
    heaplify 0, last_idx-1
  end
  self
end

def a.heaplify i, j
  t = self.lchild_idx(i)
  if t <= j
    t = self.rchild_idx(i) if t + 1 <= j && self[t + 1] > self[t]
    swap i, t if self[i] <= self[t]
    heaplify t, j
  end
end  

def swap idx1, idx2
  self[idx1],self[idx2]=self[idx2],self[idx1]
end

def a.lchild_idx i
  2 * i + 1
end

def a.rchild_idx i
  2 * i + 2
end

#ここから下はソートアルゴリズムとは関係ないです＞＜
def a.make_figure
  n = format("%b",self.size).size #段数を求める
  box = (0..n-1).map{|e| 2**e} #改行する位置を伝えるためのリスト
  tmp = self.dup
  result=box.map do |e|
    (1..e).map{tmp.shift}.join(" ")
  end
end

def a.visualize
  result=self.make_figure
  width=result.last.size
  puts "==sortを始める前のヒープはこんな感じ=="
  result.each{|e| puts e.center(width)}
  puts "======================="
end

##test
def same? target, result
  result == target.sort
end
p same?(a, a.heapsort)
p a.heapsort{|e| e.visualize}


##実行例##
# true
# ==sortを始める前のヒープはこんな感じ==
#                       93                      
#                     71 92                     
#                  62 66 81 88                  
#            60 61 65 41 77 78 85 51            
# 59 36 21 37 62 40 21 10 75 42 33 43 9 49 35 16
# =======================
# [9, 10, 16, 21, 21, 33, 35, 36, 37, 40, 41, 42, 43, 49, 51, 59, 60, 61, 62, 62, 65, 66, 71, 75, 77, 78, 81, 85, 88, 92, 93]

追記

そういえば、HeapSortの方はブロック渡せるようにしてなかった。
どちらのソートも破壊的メソッドだった。*1same?はこんな感じの方が良いかもしれない。

def same? target, result
  result == target.dup.sort_by{rand}.sort!
            #順番をかき混ぜてから標準のsortメソッドを使ってソート
end

*1:最後に「!」を付けるべきかも