L2-012 关于堆的判断（25 分)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

就是一个最小根堆。

最小根堆的性质，根节点小于等于子树的完全二叉树吧。

构建最小根堆的过程就是一个自下向上的过程。

#include<iostream>

#include<string>

#include<map>

using namespace std;

const int maxn = ;

const int inf = ;

int a[maxn], cnt;

void creat(int x){

    a[++cnt] = x;

    int t = cnt;

    while (t >  && (a[t / ] > a[t])){

        swap(a[t], a[t / ]);    t /= ;

    }

    a[t] = x;

}

int n, m, x, y;

string s;

map<int, int>p;

int main(){

    cin >> n >> m;

    for (int i = ; i <= n; ++i){ cin >> x; creat(x); }

    for (int i = ; i <= n; ++i){ p[a[i]] = i; }

    for (int i = ; i < m; ++i){

        cin >> x;

        cin >> s;

        if (s[] == 'a'){

            cin >> y >> s >> s;

            if (p[x] /  == p[y] / )cout << "T" << endl;

            else cout << "F" << endl;

        }

        else{

            cin >> s;

            cin >> s;

            if (s[] == 'r')

            { if (p[x] == )cout << "T" << endl; else cout << "F" << endl; }

            else if (s[] == 'p')

            {

                cin >> s; cin >> y; if (p[x] == p[y] / )cout << "T" << endl; else cout << "F" << endl;

            }

            else if (s[] == 'c')

            {

                cin >> s; cin >> y; if (p[x] /  == p[y])cout << "T" << endl; else cout << "F" << endl;

            }

        }

    }

}