Ruby script to generate a heap by the upward method.

heap_upward.rb

#! /usr/local/bin/ruby
# **************************************
# ヒープ作成（上方移動）
# **************************************
#
class Heap
  N = 100  # データ個数

  def initialize
    # ヒープに追加する要素の配列を生成
    @base = Array.new
    N.times { |i| @base << Random.rand(N) + 1 }
    # 乱数の種を毎回同じ値で初期化するなら以下２行のように。
    #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|
      # 元データ配列から１つヒープ要素として追加
      @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