データ構造:ハフマンツリーの解読

データ構造:ハフマンツリーの解読
ハフマンツリーの概要
1本の数のうち、いずれかのノードから別のノードに到達する経路を経路と呼び、経路変更に必要なエッジの個数を経路の長さと呼ぶ.
n個のノードとそれらの重み値を与え、それらを葉のノードとして重み付き経路長と最小のツリーを構築し、このツリーはハフマンツリーであり、最適数とも呼ばれる.
ハフマンの木の求め方

すべてのノードを集合Kに入れる.

集合K中の残りのノードが2つより大きい場合、重み値が最も小さい2つのノードを取り出し、ある新しいノードの左右のサブノードを同時に構築し、この新しいノードは彼らの共通の両親ノードであり、その重み値を2つの息子ノードの重み値と設定する.そして,その父のノードを集合Kに入れる.手順2,3を繰り返す.

集合Kに1つのノードしか残っていない場合、そのノードは構築されたハフマンツリーのルートノードであり、すべての構造で得られた中間ノードの重み値と、このハフマンツリーの重み付き力和である.

集合Kにおける重み値の最小の2つの要素を容易かつ迅速かつ効率的に求めるためには,スタックデータ構造が必要である.O(logn)の複雑さでn要素の最小要素を取得できます.スタックの実装を回避するために、標準テンプレートライブラリの対応する標準テンプレートである優先キューを使用します.priority_queue Q
このようにして構築されたスタックは、デフォルトでは大きなトップテーパですが、ハフマンツリーでは、スタックの最小要素を取得する必要があります.予算は、次の文を使用して小さなトップスタックを定義します.priority_queue,greater> Q
コードブロック

priority_queue,greater > Q;    //       

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        while(Q.empty()==false) Q.pop();        //       
        for(int i=1;i<=n;i++){                  //  n       
            int x;
            scanf("%d",&x);                     //       
            Q.push(x);
        }
        int ans=0;
        while(Q.size()>1){
            int a=Q.top();
            Q.pop();
            int b=Q.top();
            Q.pop();
            ans+=a+b;
            Q.push(a+b);
        }
        printf("%d
",ans);
    }
    return 0;
}