mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

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

[ プログラミング, 数学 ] [ Ruby ]

こんばんは。

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

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

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

1. ヒープについて

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

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

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

heap_1.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
# **************************************
# ヒープ作成(上方移動)
# **************************************
#
# ヒープクラス
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)
  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
  end
end

# メイン処理
begin
  Heap.new.generate
rescue => e
  puts "[#{e.class}] #{e.message}"
  e.backtrace.each{|trace| puts "\t#{trace}"}
  exit 1
end

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

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

heap_2.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
# **************************************
# ヒープ作成(下方移動)
# **************************************
#
# ヒープクラス
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
  end
end

# メイン処理
begin
  Heap.new.generate
rescue => e
  puts "[#{e.class}] #{e.message}"
  e.backtrace.each{|trace| puts "\t#{trace}"}
  exit 1
end

4. 実行

実際に、実行してみる。

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
$ ruby heap_1.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

$ ruby heap_2.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

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

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


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

以上。

Comments