『データ構造』C++コードスタック(優先キュー)

スタックは、優先キューで最も一般的な実装方法です.優先キューでは、各要素に優先度が付与され、キューを出るたびに最も優先度の高い要素がキューを出ます.スタックは、優先キューを格納する方法であり、特に1本のツリー形式で格納される優先キューを指す.最もよく使われるのは二叉堆ですが、データ構造を専門に紹介している以上、全部と言ってもいいです.私たちは4つの典型的な堆を取って比較して、下表を参照してください.
プロジェクト
ふたまた山
左偏樹
にこうスタック
Fibonacciスタック
ビルド
O(n)
O(n)
O(n)
O(n)
挿入
O(logn)
O(logn)
O(logn)
O(1)
さいしょうてんをとる
O(1)
O(1)
O(logn)
O(1)
最小点を削除
O(logn)
O(logn)
O(logn)
O(logn)
任意の点を削除
O(logn)
O(logn)
O(logn)
O(logn)
結合
O(n)
O(logn)
O(logn)
O(1)
スペース要件
最小
より小さい
一般
より大きい
プログラミングの複雑さ
最小
より低い
より高い
とても高い
次の点について説明します.
0、二項堆はBernoulli堆とも呼ばれ、左偏樹は左堆とも呼ばれる.斜めのスタックはテーブルにリストされていません.その複雑さは左のツリーと同じで、単独でリストする必要はありません.そのコードはより単純であるが定数が大きく,特殊なデータではO(n)に劣化する可能性がある.それは左偏樹との関係で、SplayとAVLの関係のように、優劣の区別はなく、前者はもっと簡潔で柔軟で、後者はもっと速い.また、Dスタックについては言及していません.それは、このような接触外存だけで応用に値するスタックのためです.私は言及したくありません.みんなは试験に使えないで、ふだんも使えないので、私から见るとしばらく理解して、理解すればいいので、后で本当に使ってから深く研究して遅くありません.
1、「最小点を取る」複雑度がO(log n)であり、O(1)に改善できる2つのスタック.方法は,最小ノードを随時記録し,挿入,削除およびマージなどの操作が行われた場合にのみ更新する.
2、「挿入」操作の平均時間複雑度はO(1)であり、表には最悪時間複雑度が示されている.
3、「最小点を削除」と「任意の点を削除」の2つの操作の時間複雑度は、いずれも時間複雑度を均等にするFibonacciスタック.
皆さんはすべてを理解していないかもしれませんが、自分で検索してください.私はここで実装コードを提供します.種類が多すぎるため、私はすべてのスタックに最も一般的な実装方法(例えば、二叉スタックは配列実装法だけを与える)を与えるだけで、テーマの必要に応じて融通すればいい.また,コードが長いため,比較を容易にするためにクラス版だけを与えたが,実際に実装する場合,クラスに書かないとかえって便利になることがある.
また、各要素の情報にはintの重み値が1つしかないと仮定します.これにより、煩雑なコードでぼんやり見ることなく、コードのフレームワーク構造に注目することができます.実際に使用する場合は、要素情報が多くなると、状況に応じて変更できます.
コード:

 1 //            

 2 const int maxk = 10;

 3 const int maxn = 1024;

 4 inline swap(int &x,int &y) { int t=x; x=y; y=t; }

 5 

 6 //    

 7 //    init、in、out  

 8 class Two_Heap

 9 {

10     int H[maxn+1],L; // H[1~L]     

11     void up(int j)

12     {

13         int i=j>>1;

14         if(i==0 || H[i]<H[j]) return;

15         swap(H[i],H[j]); up(i);

16     }

17     void down(int i)

18     {

19         int j=i<<1;

20         if(j<L && H[j+1]<H[j]) ++j;

21         if(j>L || H[i]<H[j]) return;

22         swap(H[i],H[j]); down(j);

23     }

24 public:

25     Two_Heap():L(0) {}

26     void init(int A[],int N)

27     {

28         //      A[1~N]     ，          ，   O(N)

29         L=N;

30         for(int i=1;i<=N;++i) H[i]=A[i];

31         for(int i=N>>1;i>=1;--i) down(i); //     ， N/2      ， N/2         

32     }

33     void in(int x) { A[++L]=x; up(L); }

34     int out() { swap(A[1],A[L--]); down(1); return A[L+1]; }

35     int min() { return A[1]; }

36 };

37 

38 //