質問編集履歴

解決

2018/11/11 18:59

投稿

opyon

スコア1009

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,3 +1,311 @@
+###解決！（タイプミスでした^^;）
+```C++
+#include <bits/stdc++.h>
+class CBTree
+{
+  private:
+    int heap_size = 0;
+    const int lowerlimit = -1;
+    std::vector<int> heap;
+    void print_key_()
+    {
+        for (int i = 1; i <= heap_size; ++i)
+        {
+            std::cout << " " << heap[i];
+        }
+        std::cout << "\n";
+    }
+    int node_L(const int &idx)
+    {
+        if (idx * 2 <= heap_size)
+        {
+            return idx * 2;
+        }
+        return 0;
+    }
+    int node_R(const int &idx)
+    {
+        if (idx * 2 + 1 <= heap_size)
+        {
+            return idx * 2 + 1;
+        }
+        return 0;
+    }
+    void maxHeapify_(const int &x)
+    {
+        int L = node_L(x);
+        int ans = heap[L] < heap[x] ? x : L;
+        if (heap_size >= 3)
+        {
+            int R = node_R(x);
+            ans = heap[ans] < heap[R] ? R : ans;
+        }
+        if (heap[ans] != heap[x])
+        {
+            std::swap(heap[ans], heap[x]);
+            maxHeapify_(ans);
+        }
+    }
+  public:
+    CBTree()
+    {
+        heap.resize(2000001, 0);
+        heap[0] = lowerlimit;
+    }
+    void push(int key)
+    {
+        heap[++heap_size] = key;
+        if (heap[1] < key)
+        {
+            std::swap(heap[1], heap[heap_size]);
+        }
+        int i = heap_size;
+        while (i > 1 && heap[i / 2] < heap[i])
+        {
+            std::swap(heap[i / 2], heap[i]);
+            i /= 2;
+        }
+    }
+    int top()
+    {
+        return heap[1];
+    }
+    void pop()
+    {
+        heap[1] = heap[heap_size];
+        --heap_size;
+        maxHeapify_(1);
+    }
+    void print_key()
+    {
+        print_key_();
+    }
+};
+void alds1_9_3()
+{
+    // 完全二分木
+    // Complete binary tree
+    // 優先順位キュー
+    // priority queue
+    CBTree T;
+    std::string s;
+    int key;
+    while (s != "end")
+    {
+        std::cin >> s;
+        if (s == "insert")
+        {
+            std::cin >> key;
+            T.push(key);
+        }
+        else if (s == "extract")
+        {
+            std::cout << T.top() << "\n";
+            T.pop();
+        }
+        // デバッグ用
+        // T.print_key();
+    }
+}
+int main()
+{
+    if (0)
+    {
+        std::cin.tie(0);
+        std::ios::sync_with_stdio(false);
+    }
+    alds1_9_3();
+    getchar();
+    return 0;
+}
+// https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_9_C
+// 入力例 1
+// insert 8
+// insert 2
+// extract
+// insert 10
+// extract
+// insert 11
+// extract
+// extract
+// end
+// 出力例 1
+// 8
+// 10
+// 11
+// 2
+```
 ###知りたいこと
 どこが間違っているのかご教示頂けると助かります。