題目大意

實作 heap，並輸出 level order

題解

能懶就懶。 C++ 有 heap 實作的函數可以用，可以不用自己寫。

push_heap 的用法是，先把元素放到陣列的最後面，再呼叫此函數即可。

由於 heap 是一個完全二元樹 (Complete Binary Tree)，因此該資料結構的 level order 就是由陣列順序直接輸出即可。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, x;
    vector<int> v;
    while (cin >> N) {
        vector<int> mhp, Mhp;
        while (N--) {
            cin >> x;
            mhp.push_back(-x);
            Mhp.push_back(x);
            push_heap(mhp.begin(), mhp.end());
            push_heap(Mhp.begin(), Mhp.end());
        }
        for (int i:mhp) cout << -i << ' ' ;
        cout << '\n';
        for (int i:Mhp) cout << i << ' ' ;
        cout << '\n';
    }
}

OJ 連結

連結：https://zerojudge.tw/ShowProblem?problemid=f498