ノードを使ったヒープ構築のプログラムを作成したいです

Question

前提・実現したいこと

各ノードにID(整数)とコスト(整数)のペアが保持され, 親ノードの保持する「コスト」が子ノードの保持する「コスト」より小さいという性質を持つヒープを構築したいです。以下の要領に従って実装したいです。

1. id（int 型）とcost（int 型）をメンバとした構造体node を定義する．
2. node を型とする大きさ３０の配列node data を（大域変数として）用意する．
3. node data の要素の初期値として，各要素のＩＤは配列のインデックス番号と同

じ値に（ID は０から２９），コストは０から１００までのランダムな値とする．
（これを関数gen node dataで行う．）
4. 上で説明したように，（また，ヒープソートでヒープを構築したように）コストに
関したヒープを構築する．（これを関数make heapで行う。)
5.（適切にヒープが構築されているかを確認するため）配列の各要素の値（ＩＤとコ
スト）を出力する．（これを関数print heap で行う．）

発生している問題

down_heap()とmake_heap()を作成したのですが, エラーは出なかったものの昇順にソートできていません。どこに原因があるのかが分からないので教えてほしいです。ノードの使い方にも慣れていないので教えてほしいです。

id: 0, cost: 30
id: 1, cost: 16   id: 2, cost: 23
id: 3, cost: 69   id: 4, cost: 13   id: 5, cost: 74   id: 6, cost: 96
id: 7, cost: 13   id: 8, cost: 89   id: 9, cost: 92   id: 10, cost: 86   id: 11, cost: 6   id: 12, cost: 12   id: 13, cost: 56   id: 14, cost: 10
id: 15, cost: 84   id: 16, cost: 78   id: 17, cost: 82   id: 18, cost: 73   id: 19, cost: 52   id: 20, cost: 95   id: 21, cost: 29   id: 22, cost: 75   id: 23, cost: 33   id: 24, cost: 24   id: 25, cost: 79   id: 26, cost: 21   id: 27, cost: 20   id: 28, cost: 48   id: 29, cost: 77
id: 0, cost: 1
id: 16, cost: 23   id: 3, cost: 4
id: 13, cost: 74   id: 6, cost: 7   id: 13, cost: 89   id: 9, cost: 10
id: 86, cost: 6   id: 12, cost: 13   id: 56, cost: 10   id: 15, cost: 84   id: 16, cost: 78   id: 17, cost: 82   id: 18, cost: 73   id: 19, cost: 52
id: 20, cost: 95   id: 21, cost: 29   id: 22, cost: 75   id: 23, cost: 33   id: 24, cost: 24   id: 25, cost: 79   id: 26, cost: 21   id: 27, cost: 20   id: 28, cost: 48   id: 29, cost: 77   id: 0, cost: 0   id: 0, cost: 0   id: 0, cost: 540410064   id: 0, cost: 0   id: 0, cost: 0

該当のソースコード

#include<iostream>
#include<random>
using namespace std;

#define N		30
#define MAX_COST	100

struct node {
	int id;
	int cost;
};

node node_data[N];

void gen_node_data()
{
	mt19937 mt{random_device{}()};
	uniform_int_distribution<int> dist(0,MAX_COST);

	for (int i=0; i<N; i++) {
		node_data[i].id = i;
		node_data[i].cost = dist(mt);
	}
}

void swap(int a[],int i,int j) 
{
	int t;
	t=a[i];
	a[i]=a[j];
	a[j]=t;
}

void down_heap(int a[],int leaf,int root)
{	
	int i=2*root;
	while (i<=leaf) {
		if (i<leaf&&a[i+1]>a[i])
			i++;
		if (a[root]>=a[i])
			break;
		swap(a,root,i);
		root=i;
		i=root*2;
	}
}

void make_heap(int a[],int asize)
{
	int i;
	for (i=asize/2-1; i>=0; i--) {
		down_heap(a,i,asize);
	}
	for (i=asize-1; i>=1; i--) {
		int t;
		t=a[0];
		a[0]=a[i];
		a[i]=t;
		down_heap(a,0,i-1);
	}
}

bool check_rightmost(int i)
{
	int x = i+2;
	while (x>1) {
		if (x%2==1) return 0;
		else x=x/2;
	}
	return 1;
}

void print_heap()
{
	for (int i=0; i<N; i++) {
		cout << "id: ";
		cout << node_data[i].id;
		cout << ", cost: ";
		cout << node_data[i].cost;

		if (check_rightmost(i)) cout << endl;
		else cout << "   ";
	}
	cout << endl;
}

int main()
{
	gen_node_data();
	print_heap();

	for (int i=0; i<N; i++) {
		make_heap(&node_data[i].cost,N)
	}
	print_heap();

	return 0;
}

試したこと

main関数でmake_heapの()内は構造体であると同時にnode_data[i]と設定し, &をつけたらエラーは出なかったのですが, &を付けないとエラーが出ました。

補足情報（FW/ツールのバージョンなど）

C++17を使用しています。

Answer 1

長文になりますがご了承ください。

1. 構造体型の配列の扱い

void make_heap(int a[],int asize)
//...
int main()
{
//...
    for (int i=0; i<N; i++) {
        make_heap(&node_data[i].cost,N)
    }
//...
}

wagashi_157さんのコードを見るに、node_dataの各要素のcostだけを取り出し、int型配列として関数に渡そうとしているようですが、そのようなことはできません。(そうしたい場合は、別に配列を作ってfor文でcostの値をコピーしてから渡す必要があります。)
関数にはnode_dataをそのまま渡し、関数内では引数をnode a[]として配列を受け取り、a[i].costのように関数内でcostを参照してください。swap関数, down_heap関数も同様です。

(修正例)

void make_heap(node a[],int asize) //node型配列として受け取る
//...
int main()
{
//...
        make_heap(node_data,N); //node型配列のまま渡す
//...
}

なお、この箇所で&をつけるとエラーが発生しない理由は、C言語では生配列を引数として渡すときは、配列そのものではなく、配列の先頭の要素を示すポインタを渡しているからです。
今回はint a[]を引数にしているので、実際に関数に渡されるのはint *(int型変数へのポインタ)型になります。一方、&は変数へのポインタのアドレスを返す演算子なので、&node_data[i].costの型もint *になります。したがって、コンパイルエラーは発生しません。

ポインタやアドレスについて詳しく知りたい場合は、こちらの記事が参考になると思います。
C++ポインタまとめ - Qiita

2. down_heap関数の処理

void down_heap(int a[],int leaf,int root)
{    
    int i=2*root;
    while (i<=leaf) {
        if (i<leaf&&a[i+1]>a[i])
            i++;
        if (a[root]>=a[i])
            break;
        swap(a,root,i);
        root=i;
        i=root*2;
    }
}

ループ(スワップ)の条件は「rootよりも子のほうがcostが小さい」です。これはwhile文で判断するには条件が複雑なので、while (true)とし、whileループ内でrootと子の大小を比較します。そして、rootよりも子のほうが小さい場合はスワップし、rootのほうが小さい場合はbreak文でループを抜けます。また、rootが子を持つかどうかの判断も必要なため、asizeを引数にします。(leaf引数は削除)

なお、ノードiの親は(i - 1) / 2、左の子はi * 2 + 1、右の子はi * 2 + 2です。ここを間違えると大変なことになります。子の取得は頻繁に行うので、関数にしておくと便利です。

(修正例)

//ノードiの左の子を返す関数
int left(int i) 
{
    return i * 2 + 1;
}
//ノードiの右の子を返す関数
int right(int i)
{
    return i * 2 + 2;
}

void down_heap(node a[], int asize, int root)
{
    int smallest; //rootと子ノードのうち最もcostが小さいノード
    while (true)
    {
        smallest = root;
        if (left(root) < asize && a[left(root)].cost < a[smallest].cost)
            smallest = left(root);  //rootが左の子を持ち、かつ左の子がsmallestよりも小さいとき
        if (right(root) < asize && a[right(root)].cost < a[smallest].cost)
            smallest = right(root); //rootが右の子を持ち、かつ右の子がsmallestよりも小さいとき

        if (smallest == root)
            break; //rootが最小ならループを抜ける
        else
        {
            //子のほうが小さいならスワップする
            swap(a, root, smallest);
            root = smallest;
        }
    }
}

3. make_heap関数の処理

void make_heap(int a[],int asize)
{
    int i;
    for (i=asize/2-1; i>=0; i--) {
        down_heap(a,i,asize);
    }
    for (i=asize-1; i>=1; i--) {
        int t;
        t=a[0];
        a[0]=a[i];
        a[i]=t;
        down_heap(a,0,i-1);
    }
}

ヒープの構築(ビルドヒープ)は、葉でないノードについて降順に((N/2-1)番目から順番に0番目まで)ダウンヒープを行うだけです。

(修正例)

void make_heap(node a[], int asize)
{
    for (int i = asize / 2 - 1; i >= 0; i--)
    {
        down_heap(a, asize, i);
    }
}

4. main関数の処理

int main()
{
    gen_node_data();
    print_heap();

    for (int i=0; i<N; i++) {
        make_heap(&node_data[i].cost,N)
    }
    print_heap();

    return 0;
}

make_heap関数内でヒープの構築は完結しているので、make_heap関数は1回呼び出すだけで良いです。あと、些細なことですがmake_heap(&node_data[i].cost,N)の末尾に;が足りません。

(修正例)

int main()
{
    gen_node_data();
    print_heap();

    make_heap(node_data, N);
    print_heap();

    return 0;
}

5. まとめ

コード全体の修正例は以下の通りです。(print_heap関数での配列の表示形式を少し変えました)

#include <iostream>
#include <random>
using namespace std;

#define N 30
#define MAX_COST 100

struct node
{
    int id;
    int cost;
};

node node_data[N];

void gen_node_data()
{
    mt19937 mt{random_device{}()};
    uniform_int_distribution<int> dist(0, MAX_COST);

    for (int i = 0; i < N; i++)
    {
        node_data[i].id = i;
        node_data[i].cost = dist(mt);
    }
}

void swap(node a[], int i, int j)
{
    node t;
    t = a[i];
    a[i] = a[j];
    a[j] = t;
}

int left(int i)
{
    return i * 2 + 1;
}
int right(int i)
{
    return i * 2 + 2;
}

void down_heap(node a[], int asize, int root)
{
    int smallest;
    while (true)
    {
        smallest = root;
        if (left(root) < asize && a[left(root)].cost < a[smallest].cost)
            smallest = left(root);
        if (right(root) < asize && a[right(root)].cost < a[smallest].cost)
            smallest = right(root);

        if (smallest == root)
            break;
        else
        {
            swap(a, root, smallest);
            root = smallest;
        }
    }
}

void make_heap(node a[], int asize)
{
    for (int i = asize / 2 - 1; i >= 0; i--)
    {
        down_heap(a, asize, i);
    }
}

bool check_rightmost(int i)
{
    int x = i + 2;
    while (x > 1)
    {
        if (x % 2 == 1)
            return 0;
        else
            x = x / 2;
    }
    return 1;
}

void print_heap()
{
    cout << "(id/cost)\n";
    for (int i = 0; i < N; i++)
    {
        cout << node_data[i].id << "/" << node_data[i].cost << " ";
        if (check_rightmost(i))
            cout << endl;
    }
    cout << endl
         << endl;
}

int main()
{
    gen_node_data();
    print_heap();

    make_heap(node_data, N);
    print_heap();

    return 0;
}

(出力例)

(id/cost)
0/29 
1/87 2/72 
3/52 4/31 5/76 6/1 
7/54 8/38 9/69 10/74 11/100 12/44 13/4 14/30 
15/25 16/63 17/95 18/48 19/74 20/57 21/54 22/83 23/65 24/39 25/22 26/73 27/97 28/2 29/97 

(id/cost)
6/1 
15/25 28/2 
8/38 4/31 25/22 13/4 
3/52 18/48 20/57 21/54 24/39 12/44 0/29 14/30 
7/54 16/63 17/95 1/87 19/74 9/69 10/74 22/83 23/65 11/100 5/76 26/73 27/97 2/72 29/97 

もしヒープについてよく分かっていないようでしたら、下記のサイトを見ることをおすすめします。ヒープの他にも様々なアルゴリズムが載っており、アルゴリズムの様子をアニメーションで説明しているので分かりやすいです。疑似コードも載っているので、コードを書く際にも役立つでしょう。
アルゴリズムビジュアル大事典

Answer 2

どこに原因があるのかを調べるのには、時間がかかりそうです。

手元にヒープソートのコードがあったので、こんなものを書いてみました。

#include <iostream> // cin, cout, endl
#include <utility>  // swap
#include <random>   // mt19937, random_device, uniform_int_distribution
using namespace std;

#define N        30
#define MAX_COST 100

struct node {
    int id;
    int cost;

	bool operator<(const node& r) const { return cost < r.cost; }
};

node node_data[N];

void gen_node_data()
{
    mt19937 mt{random_device{}()};
    uniform_int_distribution<int> dist(0, MAX_COST);
    for (int i = 0; i < N; i++) {
        node_data[i].id = i;
        node_data[i].cost = dist(mt);
    }
}

template<typename T>
void heap_sort(T& a, int n)
{
	int c, i, j, k = 0;
	while (++k < n)
		for (j = k; j > 0 && a[i = (j-1)/2] < a[j]; j = i)  // i: parent of j
			swap(a[i], a[j]);
	while (--k > 0) {
		swap(a[0], a[k]);
		for (i = j = 0; (c = (i+1)*2) <= k; i = j) {  // c: right child of i
			if (a[i] < a[c-1]) j = c-1;       // parent(i) < left child(c-1)
			if (c < k && a[j] < a[c]) j = c;  // max(parent, left) < right child(c)
			if (i == j) break;                // parent > both children
			swap(a[i], a[j]);                 // swap child and parent
		}
	}
}

bool check_rightmost(int i) { return !(i+2 & i+1); }

void print_heap()
{
    for (int i = 0; i < N; i++) {
        cout << "[" << node_data[i].id << "," << node_data[i].cost << "]";
        if (check_rightmost(i)) cout << endl;
        else cout << " ";
    }
    cout << endl;
}

int main()
{
    gen_node_data();
    print_heap();
	heap_sort(node_data, N);
    print_heap();
}

実行結果

[0,63]
[1,53] [2,3]
[3,4] [4,79] [5,4] [6,54]
[7,36] [8,97] [9,62] [10,23] [11,56] [12,28] [13,43] [14,99]
[15,19] [16,36] [17,3] [18,22] [19,96] [20,99] [21,48] [22,99] [23,40] [24,34] [25,60] [26,18] [27,9] [28,94] [29,49] 
[17,3]
[2,3] [5,4]
[3,4] [27,9] [26,18] [15,19]
[18,22] [10,23] [12,28] [24,34] [7,36] [16,36] [23,40] [13,43]
[21,48] [29,49] [1,53] [6,54] [11,56] [25,60] [9,62] [0,63] [4,79] [28,94] [19,96] [8,97] [22,99] [20,99] [14,99] 

追記
node の配列をソートしなければならないのに、質問のコードは
int の配列をソートしようとしています。修正してみました。

#include<iostream>
#include<random>
using namespace std;

#define N        30
#define MAX_COST    100

struct node {
    int id;
    int cost;
};

node node_data[N];

void gen_node_data()
{
    mt19937 mt{random_device{}()};
    uniform_int_distribution<int> dist(0,MAX_COST);

    for (int i=0; i<N; i++) {
        node_data[i].id = i;
        node_data[i].cost = dist(mt);
    }
}

void swap(node a[],int i,int j)  // ★
{
    node t;  // ★
    t=a[i];
    a[i]=a[j];
    a[j]=t;
}

void make_heap(node a[], int asize)  // ★
{
    for (int k = 0; ++k < asize; )
        for (int i, j = k; j > 0; j = i) {
			i = (j - 1) / 2;
			if (a[i].cost <= a[j].cost) break;
            swap(a, i, j);
		}
}

bool check_rightmost(int i)
{
    int x = i+2;
    while (x>1) {
        if (x%2==1) return 0;
        else x=x/2;
    }
    return 1;
}

void print_heap()
{
    for (int i=0; i<N; i++) {
        cout << "id: ";
        cout << node_data[i].id;
        cout << ", cost: ";
        cout << node_data[i].cost;

        if (check_rightmost(i)) cout << endl;
        else cout << "   ";
    }
    cout << endl;
}

int main()
{
    gen_node_data();
    print_heap();

    for (int i=0; i<N; i++) {
        make_heap(&node_data[i], N-i);  // ★
    }
    print_heap();

    return 0;
}

実行結果

id: 0, cost: 62
id: 1, cost: 29   id: 2, cost: 92
id: 3, cost: 13   id: 4, cost: 34   id: 5, cost: 38   id: 6, cost: 87
id: 7, cost: 71   id: 8, cost: 40   id: 9, cost: 7   id: 10, cost: 67   id: 11, cost: 68   id: 12, cost: 1   id: 13, cost: 67   id: 14, cost: 79
id: 15, cost: 68   id: 16, cost: 19   id: 17, cost: 31   id: 18, cost: 6   id: 19, cost: 73   id: 20, cost: 71   id: 21, cost: 93   id: 22, cost: 69   id: 23, cost: 65   id: 24, cost: 63   id: 25, cost: 1   id: 26, cost: 23   id: 27, cost: 84   id: 28, cost: 73   id: 29, cost: 1   
id: 12, cost: 1
id: 25, cost: 1   id: 29, cost: 1
id: 18, cost: 6   id: 9, cost: 7   id: 3, cost: 13   id: 16, cost: 19
id: 26, cost: 23   id: 1, cost: 29   id: 17, cost: 31   id: 4, cost: 34   id: 5, cost: 38   id: 8, cost: 40   id: 0, cost: 62   id: 24, cost: 63
id: 23, cost: 65   id: 10, cost: 67   id: 13, cost: 67   id: 15, cost: 68   id: 11, cost: 68   id: 22, cost: 69   id: 7, cost: 71   id: 20, cost: 71   id: 19, cost: 73   id: 28, cost: 73   id: 14, cost: 79   id: 27, cost: 84   id: 6, cost: 87   id: 2, cost: 92   id: 21, cost: 93   

でも、これは O(n^2・log(n)) の計算量なのでヒープソートとは言えません。

Comments

[wagashi_157]

部分ごとに分かりやすい説明をしてくださったことで上手くいかない原因が分かりました。
ありがとうございました!!