Ruby - ヒープ生成(上方・下方移動)!

Updated:


※この記事は10年以上前に投稿されたもので、情報が古い可能性があります。

前々回、前回は「ヒープ(上方移動・下方移動)」のアルゴリズムを C++ で実装することについて紹介しました。。

今回は、同じアルゴリズムを Ruby で実装してみました。(上方・下方移動)

以下、Ruby スクリプトの紹介です。

1. ヒープについてPermalink

「ヒープ」、「上方移動」、「下方移動」については前々回、前回の記事を参照ください。

2. Ruby スクリプト作成(上方移動)Permalink

以下のようにスクリプトを作成してみた。(要素はメルセンヌ・ツイスタに基づく疑似乱数で生成)

File: heap_upward.rb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#! /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

3. Ruby スクリプト作成(下方移動)Permalink

以下のようにスクリプトを作成してみた。(要素はメルセンヌ・ツイスタに基づく疑似乱数で生成)

File: heap_downward.rb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#! /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

4. 実行Permalink

まず、実行権限を付与。

$ chmod +x heap_upward.rb
$ chmod +x heap_downward.rb

そして、実行。

$ ./heap_upward.rb

#### Base

   71    84    97    53    41     4    86    55    68     8
    7    10    52    64    44    89    13    73    73     8
    4    16    94    17    87    12    40     6    37    83
   32    39    17    25    72    29    31    21    51    10
    9     7     8    64    77     5    54    92    79    42
   40    40    61    72    64    42    68    35     6    21
   96    71    71    69    14    97    43    91    12    73
   91    81    46    53    97    93    23    16    79    44
   14    13    69    86     6    15    52    43    94    64
   43    76    33    20    63    71    24     8    90    82

#### Heap

    4     4     6    12     5     8     6    13    16     6
    7    12    17    10    21    17    14    31    21     9
    7    43    16    24    41    40    40    42    35    32
   64    39    43    25    72    46    53    29    23    14
   10     8     8    53    43    33    20    71    40    82
   42    52    61    72    64    86    68    44    37    83
   96    71    71    89    69    97    55    91    84    73
   91    81    73    68    97    93    73    51    79    71
   44    13    69    86     8    15    52    64    94    77
   64    94    76    54    63    97    79    92    90    87 

$ ./heap_downward.rb

#### Tree

   29    39    30    97    77    21    74    24    85    83
  100    93    49    65    80    22    64    66    42    35
   99    79    43    85    41    38    74    76    43    90
    3    60    16    28     6    24    91    59    99    91
   27    22    62    19     4     9    85    72    53     1
   96    93    85    69    86    74    69    75    12    39
   55    26    68     8    93    47    50     1    29     1
   75    73    55    49    10    33    36    32    24    63
   91    29    37    50    58    23    28    10    91     1
   32    64    25    40    96    96    34     9    87    99

#### Heap

    1     1     1     6     1     9     3     8    10    22
    4    21    38    12    26    16    24    24    24    27
   23    10     9    30    41    49    69    69    43    39
   68    22    29    28    39    55    49    33    32    63
   29    50    28    19    32    25    40    34    53    93
   96    93    85    74    86    74    76    75    65    90
   55    80    74    60    93    47    50    64    29    97
   75    73    85    66    91    59    36    42    99    91
   91    35    37    99    58    62    83    77    91    79
  100    64    43    85    96    96    72    85    87    99

実際に配列を置き換えてみると、ヒープになっていることが確認できる。

また、上方移動と下方移動とでは同じ要素を使ってヒープを生成しても並び順は異なる。
これは、「乱数の種を同じ値で初期化」して実行してみると分かる。


ヒープについて知っておくと、ヒープを使ったソート処理(ヒープ・ソート)を行う際には役立つでしょう。

以上。





 

Sponsored Link

 

Comments