Ruby script to generate a heap by the downward method.

heap_downward.rb

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

  def initialize
    # ヒープの元になる木を生成
    @heap = [nil]
    N.times { |i| @heap << Random.rand(N) + 1 }
    # 乱数の種を毎回同じ値で初期化するなら以下２行のように。
    #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