個人用メモ

heap.rb

def downheap!(arr, i, mnode)
	a = [i, i*2+1, i*2+2]
	b = arr[a[0]]
	c = arr[a[1]]
	d = a[2] <= mnode ? arr[a[2]] : nil
	e = [b,c,d]
	e.delete(nil)

	f = e.index(e.max)
	
	arr[a[0]], arr[a[f]] = arr[a[f]], arr[a[0]]
end

def mkheap!(arr, mnode)
	m = ((mnode)/2.0).to_i

	(0..m).reverse_each{|i|
		downheap!(arr, i, mnode)
	}
end

100.times.each do
	a = 100.times.map{rand(1000)}
	mkheap!(a, a.length-1)
	if a[0] != a.max then puts 'test failed' end
end

heap_memo

ヒープの親ノードへのアクセス (n-1)/2
ヒープの子ノードへのアクセス n*2+1, n*2+2

最深ノードの親を求めるには(n-1)/2するといいのでそこから0(つまり根)までを全てダウンヒープ操作するとヒープ配列になるので最大値を配列の最後尾に移動してヒープ構造を作ってを繰り返すとソートされる
そーっとね？

参考資料:http://www.moon.sannet.ne.jp/okahisa/sort/node21.html