PriorityQueueは本当に秩序があるかどうか

2884 ワード

PriorityQueueはjdk 1である.5最初に提供される優先キューは、優先的に「整列」されたキューです.その定義によって、次のような特徴が得られます.
1.要素の順序付け、デフォルトの自然順序、つまり数字のデフォルトはキューの先頭に小さく、文字列は辞書の順序で並べられ、comparatorを定義の優先度からカスタマイズすることができます.
2.非スレッドセキュリティ、同時変更する場合に使用
java.util.concurrent.PriorityBlockingQueue

3.PriorityQueueは最小スタックに基づいて実現されたデータ構造であり、その論理構造は完全な二叉木であり、記憶構造は実際には配列である. 
4.PriorityQueueは、優先キューとも呼ばれ、先進的な先頭キューとは異なる別のキューです.キューから取り出すたびに、最も優先度の高い要素が取得されます. 
ここを見ると、TreeMap、TreeSetなどの秩序ある容器のほかに、もう一つの秩序ある容器だと思います.実際には本当にそうですか.一例を見てみましょう.
public class PriorityQueueFunc {

    public static void getPriQueueNumsAsc(){
        PriorityQueue pqueue = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        pqueue.add(10);
        pqueue.add(2);
        pqueue.add(5);
        pqueue.add(4);
        pqueue.add(9);

        System.out.println(pqueue.toString());
        
    }

    public static void main(String[] args){
        PriorityQueueFunc.getPriQueueNumsAsc();
    }


}

我々が予想した出力は[10,9,5,4,2]であった.
実際の出力:
[10, 9, 5, 2, 4]

秩序があるというのではないでしょうか.なぜ出力が完全に秩序がないのでしょうか.
priorityqueueの実装を見てみましょう.それは配列に基づいて実装された最小スタックであり、完全な二叉木であり、スタックの特性をよく知っているのは、最小スタックは左右のサブツリーがスタックトップ要素より大きいことを保証するだけですが、2つのサブ要素のどちらが大きいかは規定されていません.つまり入隊順と関係があります.
しかし、優先キューを呼ぶ以上、キューを出るときにpollメソッドで得られる要素はcomparator定義に基づいて秩序化されている.pollメソッドでスタック要素を列に並べ、調整を行います.調整後、スタックは最小の要素です.このように、キューが空になるまで、キューを出るたびに現在のスタックの最小要素(キューヘッダ要素であり、小さなトップスタックであるため、キューを出るたびに最小要素)が表示されます.要素を秩序正しく出力できます.
次の例を見てみましょう.
public class PriorityQueueFunc {

    public static void getPriQueueNumsAsc(){
        PriorityQueue pqueue = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        pqueue.add(10);
        pqueue.add(2);
        pqueue.add(5);
        pqueue.add(4);
        pqueue.add(9);

        System.out.println(pqueue.toString());

        System.out.println("===================");

        Iterator iterator = pqueue.iterator();

        while (iterator.hasNext()){
            if (pqueue.size() >1){
                System.out.print(pqueue.poll() + ", ");
            }else {
                System.out.print(pqueue.poll());
            }

        }
    }

    public static void main(String[] args){
        PriorityQueueFunc.getPriQueueNumsAsc();
    }


}

今回の出力は:
[10, 9, 5, 2, 4]
===================
10, 9, 5, 4, 2

以下はcomparatorの規定に完全に合致する順序であることがわかります.
もっと全面的に書いた文章があります.
https://www.jianshu.com/p/4c7ad59a0489