Skip to content

Instantly share code, notes, and snippets.

@komasaru komasaru/heap_downward.rb
Last active Dec 23, 2017

Embed
What would you like to do?
Ruby script to generate a heap by the downward method.
#! /usr/local/bin/ruby
# **************************************
# ヒープ作成(下方移動)
# **************************************
#
# ヒープクラス
class Heap
N = 100 # データ個数
def initialize
# ヒープの元になる木を生成
@heap = [nil]
N.times { |i| @heap << Random.rand(N) + 1 }
# 乱数の種を毎回同じ値で初期化するなら以下2行のように。
#prng = Random.new(1234)
#N.times { |i| @heap << prng.rand(N) + 1 }
display(0)
end
# ヒープ生成
def generate
n = N # データ個数
(n / 2).downto(1) do |i|
p = i # 親要素の位置
s = 2 * p # 左の子要素の位置
while s <= n
s += 1 if s < n && @heap[s + 1] < @heap[s] # 左右子要素の小さい方
break if @heap[p] <= @heap[s]
swap(p, s) # 交換
p = s # 親要素の位置
s = 2 * p # 左の子要素の位置
end
end
# 結果出力
display(1)
rescue => e
raise
end
private
# 交換
def swap(a, b)
w = @heap[a]
@heap[a] = @heap[b]
@heap[b] = w
end
# 結果出力
# param: 0 - Tree 配列
# 1 - Heap 配列
def display(k)
puts "#### #{k == 0 ? "Tree" : "Heap"}"
1.upto(N) do |i|
printf("%5d ", @heap[i])
puts if i % 10 == 0 || i == N
end
rescue => e
raise
end
end
exit 0 unless __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
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.