1。優先順位データ構造
JDK7の優先キュー（優先キュー）のデータ構造は、バイナリヒープです。正確には、それは最小の山です。
バイナリヒープは特別なヒープであり、ほぼ完全なバイナリツリーです。バイナリヒープは特性を満たします。親ノードのキー値は、常に子ノードのキー値と固定された順序関係を維持し、各ノードの左サブツリーと右サブツリーはバイナリヒープです。
最大ヒープは、親ノードのキー値が常に任意の子ノードのキー値以上に等しい場合です。最小ヒープは、親ノードのキー値が常に任意の子ノードのキー値以下である場合です。
次の図は最大ヒープです
PriorityQueueチームヘッダーは、指定された順序で最小の要素です。
PriorityQueueはヌル値を許可せず、比類のないオブジェクトをサポートしません。 PriorityQueueでは、オブジェクトをソートするために比較可能なコンパレータインターフェイスを使用する必要があり、それらの要素はソート時に優先度に応じて処理されます。
PriorityQueueのサイズはバウンドされていませんが、初期サイズは作成時に指定できます。キュー要素を追加すると、キューが自動的に展開されます。
PriorityQueueはスレッドセーフではなく、同様のPriorityBlockingQueueはスレッドセーフです。
キューはファーストインファーストアウトモードに従うことがわかっていますが、キューの優先度に基づいてオブジェクトを処理する必要がある場合があります。たとえば、毎日の取引時間中に在庫レポートを生成するアプリケーションがあります。これには、多くのデータを処理する必要があり、多くの処理時間が必要です。クライアントがこのアプリケーションにリクエストを送信すると、実際にキューに入ります。最初に優先顧客に対処し、次に通常のユーザーに対処する必要があります。この場合、JavaのPriorityQueue（優先キュー）が非常に役立ちます。
PriorityQueueは、優先度のヒープに基づいた無限のキューです。この優先キューの要素は、提供されたコンパレータによってキューがインスタンス化されたときにデフォルトで自然にソートするか、ソートすることができます。
優先キューは、ヌル値を許可せず、ユーザー定義のクラスなど、比類のないオブジェクトをサポートしません。優先キューには、オブジェクトをソートするためにJava Comparable InterfaceとComparatorインターフェイスを使用する必要があり、それらの要素はソート時に優先度に応じて処理されます。
優先キューのヘッダーは、自然な並べ替えまたはコンパレータの並べ替えに基づく最小要素です。複数のオブジェクトに同じ種類がある場合、それらのいずれかをランダムに採取することができます。キューを取得すると、キューのヘッダーオブジェクトを返します。
優先キューのサイズは無制限ですが、初期サイズは作成時に指定できます。優先キューに要素を追加すると、キューサイズが自動的に増加します。
PriorityQueueは非スレッドセーフであるため、JavaはJava Multi-Threaded環境にPriorityBlockingQueue（BlockingQueueインターフェイスの実装）を提供します。
2。優先電源コード分析
メンバー：
priavte transientオブジェクト[] queue; private int size = 0;
1.優先Queueによって小さな上部の山を構築するプロセス
ここでは、PriorityQueue Constructorを使用して、パラメーターPriorityQueue（collecntion <？extends e>の例としてコンテナ内を渡す：例：
小さなトップヒープを構築するプロセスは、ほぼ2つのステップに分かれています。
コンテナデータをコピーして、コンテナデータがnullかどうかを確認します
プライベートボイドinitelementsfromCollection（collection <？extends e> c）{object [] a = c.toarray（）; // c.toarrayが誤ってオブジェクトを返さない場合[]、コピーします。 if（a.getclass（）！= object []。class）a = arrays.copyof（a、a.length、object []。class）; int len = a.length; if（len == 1 || this.comparator！= null） this.queue = a; this.size = a.length;}データが小さなトップヒープの構造を満たすように調整します。
まず、2つの調整方法：SiftupとSiftdown
Siftdown：初期化要素が指定されている場合、要素は最小ヒープの構造特性を満たすように調整する必要があります。したがって、要素Xの重要な値は、要素Xのキー値が子供のキー値（つまり、左ノードと右のノード値よりも小さいことが保証されているか、葉のノードに該当することがわかっていることがわかっているまで、子どもと常に上から下まで交換されます。
たとえば、次の図に示すように、このノード9を調整します。
private void siftdowncomparable（int k、e x）{comparable <？ super e> key =（comparable <？super e>）x; int half = size >>> 1; // size/2は、葉のノードが到達しない限り、最初の葉のノードの添え字である（k <half）{int child =（k << 1） + 1; //左の子オブジェクトc = queue [child]; int right = child + 1; //左右の子供の最小および最小の子供を見つけます（右<size &&（（比較可能<？super e>）c）.compareto（（e）queue [右]）> 0）c = queue [child = right]; if（key.comPareTo（（e）c）<= 0）break;キュー[k] = c; k =子; } queue [k] = key;} Siftup：PriorityQueueは、新しい要素が追加されるたびに新しい要素をテールに挿入します。したがって、下部（葉）から上向きに調整することを除いて、Siftdownと同じ調整プロセスが必要です。
たとえば、次の図で次の図でキー3をノードに記入してください。
private void siftupcomparable（int k、e x）{comparable <？ super e> key =（comparable <？super e>）x; while（k> 0）{int parent =（k -1）>>> 1; //親subscriptオブジェクトe = queue [parent]; if（key.comPareto（（e）e）> = 0）break;キュー[k] = e; k =親; } queue [k] = key;}小さなトップヒープを構築する全体的なプロセスは次のとおりです。
private void initfromcollection（collection <？extends e> c）{intelementsfromCollection（c）;重い（）; }その中でも、HeapifyはSiftdownのプロセスです。
2。優先容量拡張プロセス
インスタンスメンバーからわかるように、PriorityQueueはオブジェクト[]を維持するため、その拡張方法はOrder Table ArrayListに似ています。
ここでは、成長方法のソースコードのみが記載されています
プライベートボイド成長（int mincapacity）{int oldcapacity = queue.length; //小さい場合はダブルサイズ。それ以外の場合、50％int newcapacity = oldcapacity +（（oldcapacity <64）？（oldcapacity + 2）：（ oldcapacity >> 1））; //オーバーフロー - 意識コードif（newcapacity -max_array_size> 0）newcapacity = hugecapacity（mincapacity）; queue = arrays.copyof（queue、newcapacity）; }配列の容量が大きくない場合、容量は毎回大きくないことがわかります。配列容量が64を超えると、毎回ダブルが拡張されます。
3。優先順位アプリケーション
EG1：
最も単純なアプリケーションは次のとおりです。動的データからK番目の最大数を見つけます。
アイデアは、サイズ= kで小さなトップパイルを維持することです。
//データは動的なデータ//ヒープを維持するダイナミックデータ// resは、k-most valueのパブリックブールのkthlageを保存するために使用されます（int data、int k、priorityqueue <integer> heap、int [] res）{if（heap.size（）<k）{heap.offer（data）; if（heap.size（）== k）{res [0] = heap.peek（）; trueを返します。 } falseを返します。 } if（heap.peek（）<data）{heap.poll（）; heap.offer（data）; } res [0] = heap.peek（）; trueを返します。 }
EG2：
いかなる種類も提供しないユーザークラスの顧客がいます。それを使用して優先キューを作成する場合、コンパレータオブジェクトを提供する必要があります。
customer.java
パッケージcom.journaldev.collections;パブリッククラスの顧客{private int id;プライベート文字列名;パブリックカスタマー（int i、string n）{this.id = i; this.name = n; } public int getId（）{return id; } public string getname（）{return name; }} Java乱数を使用して、ランダムなユーザーオブジェクトを生成します。自然なソートには、カプセル化されたJavaオブジェクトでもある整数オブジェクトを使用します。
PriorityQueueを使用する方法を示す最終テストコードは次のとおりです。
PriorityQueueexample.java
パッケージcom.journaldev.collections; Import java.util.comparator; import java.util.priorityqueue; Import java.util.queue; Import java.util.random; public class PriorityQueueexample {public static void main（String [] args）{// Priority Queue Natural Sortingの例queue <integer> integerpriorityQueue = new PriorityQueue <>（7）;ランダムrand = new Random（）; for（int i = 0; i <7; i ++）{integerpriorityqueue.add（new Integer（rand.nextint（100）））; } for（int i = 0; i <7; i ++）{integer in = integerpriorityqueue.poll（）; System.out.println（ "integerの処理："+in）; } //優先キューの使用例queue <customer> customerpriorityqueue = new priorityqueue <>（7、idcomparator）; adddatatoqueue（CustomerPriorityQueue）; polldatafromqueue（CustomerPriorityQueue）; } //匿名のコンパレータはpublic static Comparator <customer> idcomparator = new Comparator <compution>（）{@override public int Compare（Customer C1、Customer C2）{return（int）（c1.getid（） - c2.getid（））; }}; //キューにデータを追加するために使用されるユニバーサルメソッドプライベート静的ボイドaddDatatoQueue（Queue <customer> CustomerSpriorityQueue）{random rand = new Random（）; for（int i = 0; i <7; i ++）{int id = rand.nextint（100）; CustomerPriorityQueue.Add（New Customer（ID、 "Pankaj"+ID））; }} //キューからデータを取得するための一般的な方法Private static void polldatafromqueue（queue <customer> customerpriorityqueue）{while）{customer cust = customerpriorityqueue.poll（）; if（cust == null）break; System.out.println（ "ID ="+cust.getId（））で顧客を処理する}}}}コンパレータインターフェイスを実装し、IDベースのコンパレータを実装するJava Anonymousクラスを使用していることに注意してください。
上記のテストプログラムを実行すると、次の出力が得られます。
処理整数：9プロセス整数：16プロセス整数：18プロセス整数：25プロセス整数：33プロセシング整数：75プロセシング整数：77プロセシング顧客ID = 6プロセッシング顧客ID = ID = ID = 24Processing Customer with ID = 22Processing Customer ID = ID = 96の顧客を処理する顧客
出力の結果から、次に最小の要素が最初にキューの頭で取り出されることが明確にわかります。 Compantatorが実装されていない場合、customerPriorityQueueを作成するときにClassCastExceptionがスローされます。
スレッド「Main」java.lang.classcastexception：com.journaldev.collections.customerはjava.util.util.priorityqueue.siftupcomparableでjava.lang.comparableにキャストすることはできません（priorityque.java:633）at java.util.util.priority.siftuue.siftuue.siftup（pirritiale.java.java.java.java.java.java.java. java.util.priorityqueue.offer（priorityqueue.java:329）at java.util.priorityqueue.add（priorityqueue.java:306）at com.journaldev.collections.priorityqueueexample.addatatatoue（priorityqueueexamepame.java:45）at com.journaldev.collections.priorityqueueexample.main（priorityqueueexample.java:25）