寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)

アルゴ式(beta版)の「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ) からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)

僕が作成、提出したコードは、以下のとおりです。

Q1. 二分木の通りがけ順

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q1. 二分木の通りがけ順
https://algo-method.com/tasks/913
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> num;
void f(ll v,vector<ll> &l,vector<ll> &r){
    if(l[v]!=-1){
        f(l[v],l,r);
    }
    num.push_back(v);
    if(r[v]!=-1){
        f(r[v],l,r);
    }
}
int main(void){
    ll n;
    cin>>n;
    vector<ll> l(n),r(n);
    for(ll i=0;i<n;i++){
        cin>>l[i]>>r[i];
    }
    f(0,l,r);
    for(ll i=0;i<n;i++){
        cout<<num[i]<<(i==n-1 ? "\n" : " ");
    }
    return 0;
}
Q3. 二分探索木への挿入 (2)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q3. 二分探索木への挿入 (2)
https://algo-method.com/tasks/918
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node{
    Node* parent;
    Node* left;
    Node* right;
    ll val;
    Node(const ll& val=0):val(val){
        parent=nullptr;
        left=nullptr;
        right=nullptr;
    }
};
Node* root=new Node();
void insert(Node* node_a){
    ll a=node_a->val;
    Node* par,*next=root;
    while(next){
        par=next;
        if(a<=par->val){
            next=par->left;
        }else{
            next=par->right;
        }
    }
    if(a<=par->val){
        node_a->parent=par;
        par->left=node_a;
    }else{
        node_a->parent=par;
        par->right=node_a;
    }
}
vector<ll> num;
void f(Node* node){
    num.push_back(node->val);
    if(node->left){
        f(node->left);
    }
    if(node->right){
        f(node->right);
    }
}
int main(void){
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll v;
        cin>>v;
        if(i==0){
            root->val=v;
            continue;
        }
        Node *node_a=new Node(v);
        insert(node_a);
    }
    f(root);
    assert(num.size()==q);
    for(ll i=0;i<q;i++){
        cout<<num[i]<<((i==q-1) ? "\n" : " ");
    }
    return 0;
}
Q4. 二分探索木のキー検索

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q4. 二分探索木のキー検索
https://algo-method.com/tasks/919
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node{
    Node* parent;
    Node* left;
    Node* right;
    ll val;
    Node(const ll& val=0):val(val){
        parent=nullptr;
        left=nullptr;
        right=nullptr;
    }
};
Node *root=new Node(-1);
void insert(Node *node_a){
    ll a=node_a->val;
    Node* par,*next=root;
    while(next){
        par=next;
        if(a<=par->val){
            next=par->left;
        }else{
            next=par->right;
        }
    }
    if(a<=par->val){
        node_a->parent=par;
        par->left=node_a;
    }else{
        node_a->parent=par;
        par->right=node_a;
    }
}
bool tf(ll v){
    Node *now=root;
    while(now){
        if(now->val==v){
            return true;
        }
        if(v<=now->val){
            now=now->left;
        }else{
            now=now->right;
        }
    }
    return false;
}
int main(void){
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll num,v;
        cin>>num>>v;
        if(num==0){
            Node *node_v=new Node(v);
            insert(node_v);
        }else{
            if(tf(v)){
                cout<<"Yes"<<endl;
            }else{
                cout<<"No"<<endl;
            }
        }
    }
    return 0;
}
Q7. 強平衡二分木の頂点数

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q7. 強平衡二分木の頂点数
https://algo-method.com/tasks/922
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll h;
    cin>>h;
    ll mini=1;
    for(ll i=0;i<h;i++){
        mini*=2;
    }
    ll maxi=2*mini-1;
    cout<<mini<<" "<<maxi<<endl;
    return 0;
}
Q8. 完全二分木の頂点番号

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q8. 完全二分木の頂点番号
https://algo-method.com/tasks/923
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll h;
    cin>>h;
    ll n=1;
    for(ll i=0;i<=h;i++){
        n*=2;
    }
    n--;
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll t,v;
        cin>>t>>v;
        ll ans=-1;
        if(t==0){
            if(v!=0){
                ans=(v-1)/2;
            }
        }else if(t==1){
            ans=2*v+1;
            if(ans>=n){
                ans=-1;
            }
        }else{
            ans=2*(v+1);
            if(ans>=n){
                ans=-1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
Q9. ヒープかどうか

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q9. ヒープかどうか
https://algo-method.com/tasks/924
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    bool tf=true;
    for(ll i=1;i<n;i++){
        ll j=(i-1)/2;
        if(a[j]<a[i]){
            tf=false;
        }
    }
    cout<<(tf ? "Yes" : "No")<<endl;
    return 0;
}
Q10. ヒープへの挿入

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q10. ヒープへの挿入
https://algo-method.com/tasks/925
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll q;
    cin>>q;
    vector<ll> heap;
    for(ll i=0;i<q;i++){
        ll v;
        cin>>v;
        heap.push_back(v);
        ll j=i;
        while(j>0){
            ll par=(j-1)/2;
            if(heap[par]<heap[j]){
                swap(heap[par],heap[j]);
                j=par;
            }else{
                break;
            }
        }
    }
    for(ll i=0;i<heap.size();i++){
        cout<<heap[i]<<((i==heap.size()-1) ? "\n" : " ");
    }
    return 0;
}
Q11. ヒープからの削除

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q11. ヒープからの削除
https://algo-method.com/tasks/926
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll q;
    cin>>q;
    vector<ll> heap;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            ll v;
            cin>>v;
            heap.push_back(v);
            ll j=heap.size()-1;
            while(j>0){
                ll par=(j-1)/2;
                if(heap[par]<heap[j]){
                    swap(heap[par],heap[j]);
                    j=par;
                }else{
                    break;
                }
            }
        }else{
            ll ans=heap[0];
            cout<<ans<<endl;
            heap[0]=heap.back();
            heap.pop_back();
            ll j=heap.size();
            ll k=0;
            while(k<j){
                ll l=2*k+1,r=2*(k+1);
                ll tf=0;
                ll maxi=heap[k];
                if(l<j && heap[l]>maxi){
                    maxi=heap[l];
                    tf=1;
                }
                if(r<j && heap[r]>maxi){
                    maxi=heap[r];
                    tf=2;
                }
                if(tf==0){
                    break;
                }else if(tf==1){
                    swap(heap[k],heap[l]);
                    k=l;
                }else{
                    swap(heap[k],heap[r]);
                    k=r;
                }
            }
        }
    }
    return 0;
}
Q12. タスクリスト (3)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」9章:二分木 (二分探索木、ヒープ)
Q12. タスクリスト (3)
https://algo-method.com/tasks/927
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using lls=tuple<ll,ll,string>;
int main(void){
    ll q;
    cin>>q;
    priority_queue<lls,vector<lls>,greater<lls>> pq;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            ll d;string s;
            cin>>d>>s;
            pq.emplace(d,i,s);
        }else{
            auto [d,j,s]=pq.top();
            pq.pop();
            cout<<s<<endl;
        }
    }
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com