Skip to content

Instantly share code, notes, and snippets.

@komasaru komasaru/heap_upward.rb
Last active Apr 19, 2018

Embed
What would you like to do?
Ruby script to generate a heap by the upward method.
#! /usr/local/bin/ruby
# **************************************
# ヒープ作成(上方移動)
# **************************************
#
class Heap
N = 100 # データ個数
def initialize
# ヒープに追加する要素の配列を生成
@base = Array.new
N.times { |i| @base << Random.rand(N) + 1 }
# 乱数の種を毎回同じ値で初期化するなら以下2行のように。
#prng = Random.new(1234)
#N.times { |i| @base << prng.rand(N) + 1 }
display(0)
# ヒープ用配列
@heap = Array.new(N + 1)
end
# ヒープ生成
def generate
1.upto(N) do |n|
# 元データ配列から1つヒープ要素として追加
@heap[n] = @base[n - 1]
s = n # 追加要素の位置
p = s / 2 # 親要素の位置
while s >= 2 && @heap[p] > @heap[s]
w = @heap[p]
@heap[p] = @heap[s]
@heap[s] = w
s = p # 追加要素の位置
p = s / 2 # 親要素の位置
end
end
# 結果出力
display(1)
rescue => e
raise
end
private
# 結果出力
# param: 0 - Base 配列
# 1 - Heap 配列
def display(k)
puts "#### #{k == 0 ? "Base" : "Heap"}"
k.upto(N - 1 + k) do |i|
printf("%5d ", k == 0 ? @base[i]: @heap[i])
puts if (i + 1 - k) % 10 == 0 || i == N - 1 + k
end
rescue => e
raise
end
end
if __FILE__ == $0
begin
Heap.new.generate
rescue => e
puts "[#{e.class}] #{e.message}"
e.backtrace.each{|trace| puts "\t#{trace}"}
exit 1
$stderr.puts "[#{e.class}] #{e.message}"
e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.