JavaのPriorityQueueではまった（間違った順序で要素を返すように見えた）話

結論：優先度が適用された順序で取得するには、poll()やpeek()を使いましょう

それ以外のメソッドを使うと、順序が保証されません。

• iterator() →×

• toArray() →×

• toString() →×

• poll() →○

• peek() →○

参考:https://docs.oracle.com/javase/jp/8/docs/api/java/util/PriorityQueue.html

悪い例

bad_example1.java

import java.util.*;

int[] data = new int[]{10,1,1000,100,10000};
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < data.length; i++) {
  pq.add(data[i]);
}
System.out.println(pq);  //toString()が適用される
Iterator<Integer> itr = pq.iterator();
while(itr.hasNext()) {
  System.out.println(itr.next());
}

出力結果:順序が保証されない（環境によって結果が異なる）
[10,1000,1,10000,100]
10
1000
1
10000
100

良い例

good_example1.java

import java.util.*;

int[] data = new int[]{10,1,1000,100,10000};
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < data.length; i++) {
  pq.add(data[i]);
}
while(!pq.isEmpty()) {
  System.out.println(pq.poll());
}

出力結果:順序が保証される
1
10
100
1000
10000

余談

AtCoderのコンテストに参加している時に、手元では動作するのに提出するとWAになり混乱。デバッグしてみると、最初「PriorityQueue が間違った順序で要素を返す」ように見えましたが、よくよく調べてみると上記の仕様でした(^^;