###解決!(タイプミスでした^^;)
C++
1#include <bits/stdc++.h> 2 3class CBTree 4{ 5 private: 6 int heap_size = 0; 7 const int lowerlimit = -1; 8 std::vector<int> heap; 9 10 void print_key_() 11 { 12 for (int i = 1; i <= heap_size; ++i) 13 { 14 std::cout << " " << heap[i]; 15 } 16 std::cout << "\n"; 17 } 18 19 int node_L(const int &idx) 20 { 21 if (idx * 2 <= heap_size) 22 { 23 return idx * 2; 24 } 25 return 0; 26 } 27 28 int node_R(const int &idx) 29 { 30 if (idx * 2 + 1 <= heap_size) 31 { 32 return idx * 2 + 1; 33 } 34 return 0; 35 } 36 37 void maxHeapify_(const int &x) 38 { 39 int L = node_L(x); 40 int ans = heap[L] < heap[x] ? x : L; 41 if (heap_size >= 3) 42 { 43 int R = node_R(x); 44 ans = heap[ans] < heap[R] ? R : ans; 45 } 46 if (heap[ans] != heap[x]) 47 { 48 std::swap(heap[ans], heap[x]); 49 maxHeapify_(ans); 50 } 51 } 52 53 public: 54 CBTree() 55 { 56 heap.resize(2000001, 0); 57 heap[0] = lowerlimit; 58 } 59 60 void push(int key) 61 { 62 heap[++heap_size] = key; 63 if (heap[1] < key) 64 { 65 std::swap(heap[1], heap[heap_size]); 66 } 67 68 int i = heap_size; 69 while (i > 1 && heap[i / 2] < heap[i]) 70 { 71 std::swap(heap[i / 2], heap[i]); 72 i /= 2; 73 } 74 } 75 76 int top() 77 { 78 return heap[1]; 79 } 80 void pop() 81 { 82 heap[1] = heap[heap_size]; 83 --heap_size; 84 maxHeapify_(1); 85 } 86 void print_key() 87 { 88 print_key_(); 89 } 90}; 91 92void alds1_9_3() 93{ 94 // 完全二分木 95 // Complete binary tree 96 // 優先順位キュー 97 // priority queue 98 CBTree T; 99 100 std::string s; 101 int key; 102 while (s != "end") 103 { 104 std::cin >> s; 105 if (s == "insert") 106 { 107 std::cin >> key; 108 T.push(key); 109 } 110 else if (s == "extract") 111 { 112 std::cout << T.top() << "\n"; 113 T.pop(); 114 } 115 // デバッグ用 116 // T.print_key(); 117 } 118} 119 120int main() 121{ 122 if (0) 123 { 124 std::cin.tie(0); 125 std::ios::sync_with_stdio(false); 126 } 127 alds1_9_3(); 128 getchar(); 129 return 0; 130} 131 132// https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_9_C 133 134// 入力例 1 135// insert 8 136// insert 2 137// extract 138// insert 10 139// extract 140// insert 11 141// extract 142// extract 143// end 144 145// 出力例 1 146// 8 147// 10 148// 11 149// 2
###知りたいこと
どこが間違っているのかご教示頂けると助かります。
###現状・試したこと
T.push()メソッド経由で配列に数値を代入出来ないのに、
T.heap[2]=222などで直接配列に代入すると正常に更新出来ます。
処理途中にデバッグ出力してみたのですが 配列名[インデックス] = 数値で,
同じように代入しているのに代入されていない意味が理解できません。
型の不一致を避けるために全てint型に変更しましたが同じです。
T.push(111); prt(T.heap[1]); T.heap[2] = 222; prt(T.heap[2]);
※以下マクロを使用しています。見づらいコードですみません。
prt()
prt2()
###サンプルコード(質問で動作させられる部分のみ)
C++
1#include <bits/stdc++.h> 2#define prt(x) std::cout << x << std::endl; 3#define prt2(x) std::cout << " " << x; 4 5class CBTree 6{ 7 public: 8 int heap_size; 9 const int lowerlimit = -1; 10 int heap[100]; 11 12 CBTree() 13 { 14 heap_size = 0; 15 heap[0] = lowerlimit; 16 } 17 void push(int key) 18 { 19 // debug 20 21 prt2("heap[0]:") 22 prt(heap[0]); 23 24 ++heap_size; 25 heap[heap_size] == key; 26 27 // heap[1] == key; 28 // 要素番号を直接指定しても同じ 29 30 prt2("heap_size:"); 31 prt2(heap_size); 32 prt2("heap[i]:"); 33 prt2(heap[heap_size]); 34 prt2("key:"); 35 prt2(key); 36 prt(""); 37 38 // debug 39 } 40}; 41 42void alds1_9_3() 43{ 44 // 完全二分木 45 // Complete binary tree 46 // 優先順位キュー 47 // priority queue 48 CBTree T; 49 50 std::string s; 51 int key; 52 53 T.push(111); 54 prt(T.heap[1]); 55 56 T.heap[2] = 222; 57 prt(T.heap[2]); 58} 59 60int main() 61{ 62 alds1_9_3(); 63 getchar(); 64 return 0; 65} 66
期待する出力
heap[0]:-1 heap_size: 1 heap[i]: 111 key: 111 111 222
現状の出力(32761の値は不定)
heap[0]:-1 heap_size: 1 heap[i]: 32761 key: 111 32761 222
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/11/11 15:26
2018/11/11 15:27
2018/11/11 15:29
2018/11/11 18:51
2018/11/12 06:06
2018/11/12 06:16
2018/11/12 06:19 編集
2018/11/12 06:29
2018/11/12 08:18
2018/11/12 08:30