PriorityQueue의 toString 메소드가 요소 순서 해석을 잘못 이끄는 ​​방법

Java에서 PriorityQueue 데이터 구조는 할당된 요소에 따라 요소의 우선순위를 지정하기 위해 이진 힙을 유지합니다. 비교 전략. 이 전략은 제공된 코드 조각에서 볼 수 있듯이 일반적으로 사용자 지정 비교기를 통해 구현됩니다. 그러나 PriorityQueue의 toString 메서드 출력을 검사할 때 요소 순서에 관한 일반적인 오해가 있습니다.

toString 메서드는 PriorityQueue 콘텐츠의 텍스트 표현을 제공하도록 설계되었습니다. 그러나 비교기에 의해 정의된 우선순위 순서를 암시적으로 적용하지는 않습니다. 대신 예상되는 정렬 순서와 정렬되지 않을 수 있는 힙 내의 현재 위치에 요소를 표시하기만 합니다.

주어진 예에서 PriorityQueue는 빈도 값의 우선순위를 지정하기 위해 사용자 정의 비교기로 초기화됩니다. 이 순서를 반영하여 출력에 빈도가 낮은 요소가 먼저 나열되도록 의도했습니다. 그러나 toString 메서드의 출력에는 잘못된 순서가 표시되어 의도한 우선순위와 분명히 모순됩니다.

이러한 불일치의 원인은 바이너리 힙의 내부 구조에서 비롯됩니다. 부분 순서를 유지하지만 요소는 힙에서 제거될 때까지 완전히 정렬되지 않습니다. toString 메소드는 이 정렬을 수행하지 않고 힙에서 직접 요소를 검색하여 관찰된 출력으로 이어집니다.

이 문제를 해결하고 올바른 정렬 순서를 얻으려면 PriorityQueue에서 요소를 하나씩 추출해야 합니다. 하나. poll() 메소드는 이를 수행하여 힙에서 요소를 제거하고 이를 반환합니다. poll()을 사용하여 PriorityQueue를 반복하고 반환된 요소를 인쇄하면 의도한 대로 정렬된 순서를 얻을 수 있습니다.

따라서 정렬된 순서로 요소를 인쇄하는 올바른 코드는 다음과 같습니다.

while (!queue.isEmpty()) {
   System.out.println(queue.poll());
}

이것은 비교기에 정의된 대로 주파수의 오름차순으로 요소를 인쇄합니다.