mk-mode BLOG

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

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

C++ - ヒープ生成(下方移動)!

[ プログラミング, 数学 ] [ C言語 ]

こんばんは。

前回は「ヒープ」の生成を「上方移動」で行うアルゴリズム、C++ での実装について紹介しました。

今回は「下方移動」によるヒープの生成についてです。

以下、簡単な説明と C++ ソースコードの紹介です。

1. ヒープについて

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

2. ヒープ生成方法(下方移動)

下方移動のアルゴリズムは、

  • まず、上方移動同様、上位の親要素から順に配列化して考える。
  • 子要素を持つ最後の親要素から順に上位へ以下の処理を繰り返す。
    • 親要素のほうが子要素より小さければ、2つの子要素のうち小さい方と親要素を交換する。
    • 交換した子要素を新たな親要素とし、親要素 < 子要素 の関係を満たす間、下方のループに対して同じ処理を繰り返す。

HEAP_4

3. C++ ソースコード作成

以下のようにソースコードを作成してみた。(要素は乱数で生成)

Heap2.cpp
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/***********************************************************
 * ヒープ生成(下方移動)
 **********************************************************/
#include <cstdlib>   // for srand()
#include <iostream>  // for cout
#include <stdio.h>   // for printf()

#define N 100        // データ個数

using namespace std;

/*
 * ヒープクラス
 */
class Heap
{
    // 各種変数
    int n, i, s, p, w;            // Loop インデックス等
    int heap[N + 1];              // 木(後のヒープ)用配列

    public:
        Heap();                   // コンストラクタ
        void generate();          // ヒープ生成
    private:
        void swap(int *, int *);  // 要素交換
};

/*
 * コンストラクタ
 */
Heap::Heap()
{
    // ヒープの元になる木を生成
    srand((unsigned int)time(NULL));
    printf("#### Tree\n");
    for (i = 1; i <= N; i++) {
        heap[i] = rand() % N + 1;
        printf("%5d ", heap[i]);
        if (i % 10 == 0) printf("\n");
    }
    printf("\n");
}

/*
 * ヒープ生成
 */
void Heap::generate()
{
    n = N;              // データ個数
    for (i = n / 2; i >= 1; i--) {
        p = i;          // 親要素の位置
        s = 2 * p;      // 左の子要素の位置
        while (s <= n) {
            if (s < n && heap[s + 1] < heap[s]) s++;  // 左右子要素の小さい方
            if (heap[p] <= heap[s]) break;
            swap(&heap[p], &heap[s]);
            p = s;      // 親要素の位置
            s = 2 * p;  // 左の子要素の位置
        }
    }

    // 結果出力
    printf("#### Heap\n");
    for (i = 1; i <= n; i++) {
        printf("%5d ", heap[i]);
        if (i % 10 == 0) printf("\n");
    }
    printf("\n");
}

void Heap::swap(int *a, int *b)
{
    w  = *a;
    *a = *b;
    *b = w;
}

/*
 * メイン処理
 */
int main()
{
    try
    {
        // ==== インスタンス化
        Heap objHeap;

        // ==== ヒープ生成
        objHeap.generate();
    }
    catch (...) {
        // ==== 異常終了
        cout << "例外発生!" << endl;
        return -1;
    }

    // ==== 正常終了
    return 0;
}

4. C++ ソースコンパイル

以下のコマンドで C++ ソースをコンパイルする。
(-Wall は警告出力、-O2 最適化のオプション)

1
$ g++ -Wall -O2 -o Heap2 Heap2.cpp

何も出力されなければ成功。

5. 実行

実際に、実行してみる。

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
$ ./Heap2

#### Tree

   12    36    56    34     3    41    14    99    43    36
   84    66    54    40    29    88    65    47    67    56
   71     3    73    86    60     7    30    12    57    41
    2    68    29    57     1    83    50    67    82    44
    2    17     9     7    56    38    94    20    36    61
   28     7    15   100    44    74     6    25    37    63
   17    38    82    97    47    35    80    48    53    13
   91     6    29    99    12    84    88     6    56    24
   18    83    82    84    82    25     9    39     1    46
    1    17    35    35    66    33    21    45    80    73

#### Heap

    1     1     2     6     1     7     6    13     6     2
    3    20     7    12    14    29    34    12    36    18
    9     3    17    21    28    15    30    40    25    17
   29    47    35    48    65    29    43    67    56    24
   56    17     9     7    46    35    35    33    36    61
   60    54    41   100    44    74    56    57    37    63
   41    38    82    97    68    88    80    57    53    99
   91    83    47    99    50    84    88    82    67    36
   44    83    82    84    82    25    71    39    12    84
   56    38    73    94    66    66    86    45    80    73

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


あらかじめ配列が用意されている場合は、今回の下方移動の方が良いかも知れません。

以上。

Comments