Java의 PriorityQueue에서이 이상한 순서가 발생하는 이유는 무엇입니까?

Question

나는 설명서와 내가 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 

Answer 1

PriorityQueue는 첫 번째 요소가 작은 것을 보장한다.

binary heap 각 하위 힙 (하위 트리)에만 루트가 가장 작은 요소임을 보장합니다.
힙은 실제로 완전한 트리 (또는이 트리의 배열 표현)입니다. 조건 (루트보다 작음)을 위반하는 요소를 삽입 할 때마다 오래된 루트가 다운됩니다. 이것은 힙에 대해 재귀 적으로 수행됩니다.

이 부분 오더링은 각 시점에서 min 요소 만 필요한 경우 사용할 수있는 빠르고 캐시 효율적인 (배열 표현과 함께) 데이터 구조를 허용합니다.

Answer 2

PriorityQueue 인 첫번째 요소가 작은 것을 보장 구조처럼 나무이다. 다른 요소의 순서는 중요하지 않으며 PQ가 트리의 균형을 유지하는 방식 때문일 수 있습니다. @larsmans 지적한 바와

이것은 최소 힙 순서로 알려져

Answer 3

자바 문서는 :

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과 같은 주문입니다.