C++ source code to generate a heap with the downward method.

heap_downward.cpp

/***********************************************************
 * ヒープ生成（下方移動）
 **********************************************************/
#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;
}