プログラミング勉強基礎　その２

前回は、挿入ソートとマージソートの二つをRubyで書きました。
こんなのはとっくの前に習ってるはずだけど、意外とコーディングが面白い。就活中は変に飛ばして学習するより、こういうのやるのもいいかな、と思えてきました。
ということで今回はヒープソート。このヒープはプライオリティキュー等の応用、挿入等が便利なため、クイックソートがある現在でも良く使われる手法。アルゴリズム・イントロダクションでは関数をそれぞれの機能に分けて解説がされており、非常に分かりやすかった。
以下Ruby ソースコード。



#ヒープ

def parent(i)

  return i/2-1

end

def left(i)

  return 2*i+1

end

def right(i)

  return 2*i+2

end

#指定した枝の位置を正しい位置へ移動する

def heapify(a,i)

  l=left(i)

  r=right(i)

  if l<=a.length && a[l]!=nil && a[l]>a[i]

    largest=l

  else

    largest=i

  end

  if r<=a.length && a[r]!=nil && a[r]>a[largest]  

    largest=r

  end

  if largest!=i

    a[i],a[largest]=a[largest],a[i]

    heapify(a,largest)

  end

end

#バラバラな配列からヒープを作る

def build_heap(a)

  heap_size=a.length

  (a.length/2).downto(0) do |n|

    heapify(a,n)

  end

end

#ソート。一番下の要素を取り出すのを繰り返す

def heap_sort(a)

  build_heap(a)

  output=[]

  len=a.length

  len.step(1,-1) do |n|

    a[0],a[n-1]=a[n-1],a[0]

    output.push(a.pop)

    heapify(a,0)

  end

  p output

end

#木に要素を挿入する

def heap_insert(a,key)

  i=a.length

  a.push(key)

  while(i>1 && a[parent(i)]<key)

    a[i],a[parent(i)]=a[parent(i)],a[i]

    i=parent(i)

  end

end