2

ドキュメントとPriorityQueueについて見つけたすべてのものを読みましたが、出力が非常に奇妙である理由がわかりません。つまり、順序を追加するポイントが得られないということです。誰か説明できますか?

PriorityQueue<String> pq = new PriorityQueue<String>();
pq.offer("2"); 
System.out.println("add 2 : " + pq); 
pq.offer("4");
System.out.println("add 4 : " + pq);
System.out.println(pq.peek() + " ");
pq.offer("1");
System.out.println("offer 1 : " + pq);
pq.offer("3");
System.out.println("add 3 : " + pq);
pq.remove("1");
System.out.println("remove 1 : " + pq);

出力：

add 2 : [2]
add 4 : [2, 4]            <- why 4 goes there
offer 1 : [1, 4, 2]       <- why 1 goes first
add 3 : [1, 3, 2, 4]      <- why reorder
remove 1 : [2, 3, 4]      <- again
4

3 に答える 3

3

PriorityQueue最初の要素が最小であることのみを保証します。

バイナリ ヒープは、各サブヒーブ (サブツリー) でルートが最小の要素であることのみを保証します 。
ヒープは実際には完全なツリー (またはその配列表現) です。条件に違反する (ルートよりも小さい) 要素を挿入すると、古いルートがふるいにかけられます。これはヒープ上で再帰的に行われます。

この部分的な順序付けにより、各時点で最小要素のみが必要な場合に使用できる、高速で比較的キャッシュ効率の高い (配列表現による) データ構造が可能になります。

于 2012-09-11T12:01:46.210 に答える
2

PriorityQueue はツリーのような構造で、最初の要素が最小になるようにします。他の要素の順序は重要ではなく、PQ がツリーのバランスをとる方法による可能性があります。

@larsmans が指摘しているように、これは最小ヒープ順序として知られています

于 2012-09-11T12:01:15.107 に答える
2

Java ドキュメント:

An unbounded priority queue based on a priority heap. 
The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. 
A priority queue does not permit null elements. 
A priority queue relying on natural ordering also does not permit insertion of 
non-comparable objects (doing so may result in ClassCastException).

また、次のようにも述べています。

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

あなたが出力しているのはtoString()メソッドです。出力は、そのメソッドがツリーを反復する方法によるものです。と同じ順序Iteratorです。

于 2012-09-11T12:03:21.627 に答える