Java PriorityQueue Iterator가 순서대로 순회를 보장하지 않는 이유는 무엇입니까?

PriorityQueue 순회 순서 호기심

Java PriorityQueue 클래스는 놀랍게도 특정 순회를 보장하지 않는 내장 반복자를 제공합니다. 주문하다. 표준에서 벗어나면 다음과 같은 질문이 제기됩니다. PriorityQueue 반복자는 왜 이런 식으로 동작합니까?

Java 문서를 자세히 살펴보면 다음 구절을 접하게 됩니다.

"이 클래스와 해당 반복자는 모든 것을 구현합니다. Collection 및 Iterator 인터페이스의 선택적 메소드 중 iterator() 메소드에 제공된 Iterator는 특정 순서로 우선순위 큐의 요소를 순회하는 것을 보장하지 않습니다. 순회하려면 Arrays.sort(pq.toArray()) 사용을 고려하십시오."

근본적인 이유는 PriorityQueue에서 사용하는 데이터 구조에 있습니다. 배열이나 연결된 목록과 같은 데이터 구조와 달리 PriorityQueue는 가장 작거나 가장 큰 요소 검색에 우선 순위를 두는 이진 힙을 활용합니다. 그러나 이러한 우선순위에는 비용이 따릅니다. 힙의 특성으로 인해 해당 요소의 순서화된 순회를 제공하는 효율적인 알고리즘이 없습니다.

바이너리 힙에서 가장 작은 요소는 루트에 있으며, 제거되면 힙은 다음과 같습니다. 다음으로 가장 작은 요소를 루트로 올리기 위해 재조정됩니다. 이러한 상수 재정렬은 정렬된 순회를 비현실적으로 만듭니다.

따라서 PriorityQueue 반복자는 요소가 반환되는 순서에 대한 보장을 제공하지 않고 데이터 구조를 순회하도록 설계되었습니다. 순서대로 순회하려면 PriorityQueue의 배열 표현에 Arrays.sort()와 같은 외부 메서드를 사용해야 합니다.

위 내용은 Java PriorityQueue Iterator가 순서대로 순회를 보장하지 않는 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!