回答編集履歴

追記

2021/11/05 01:10

投稿

kazuma-s

スコア8224

test CHANGED Viewed

@@ -161,3 +161,199 @@
 [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 の配列をソートしようとしています。修正してみました。
+```C++
+#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;
+}
+```
+実行結果
+```text
+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)) の計算量なのでヒープソートとは言えません。