PriorityQueue보다 TreeMap을 사용해야하는 경우는 언제입니까?

Question

둘 다 Prim의 알고리즘에 필요한 최소값을 검색하도록하고, 값을 업데이트하기 위해 키를 제거하고 다시 삽입하도록합니다. 이 예제뿐만 아니라 일반적으로 말하면 다른 것을 사용하는 이점이 있습니까?

Answer 1

일반적으로 말하면 힙을 사용하여 최소 요소 만 추적하는 것이 적습니다.

트리가 더 체계적이며 조직을 유지 관리하기 위해 더 많은 계산이 필요합니다. 그러나 키에 액세스해야하고 최소값 일 필요가없는 경우 힙으로 충분하지 않으며 트리의 추가 오버 헤드가 정당화됩니다.

Answer 2

우선 순위 대기열을 구현하는 방법에 따라 다릅니다. Cormen의 2 집 ed에 따르면 가장 빠른 결과는 Fibonacci Heap입니다.

Answer 3

차이점 중 하나는 정상 힙 기반의 PriorityQueue (Oracle의 경우)에서는 선형 O (N)이지만 TreeSet/Map에서는 O (log (N)) 인 경우 remove (Object) 및 contains

많은 수의 요소가 있고 remove (Object) 또는 contains (Object)를 많이 수행하면 TreeSet/Map이 빠를 수 있습니다.

Answer 4

우선 순위 큐에서 Erickson과 완전히 동의한다는 것은 최소/최대 요소 만 제공한다는 것입니다.

또한 우선 순위 큐는 데이터의 전체 순서를 유지하는 데 덜 강력하기 때문에 일부 특수한 경우에 이점이 있습니다. 가장 큰 M 요소를 N의 배열로 추적하려는 경우 시간 복잡도는 O(N*LogM)이고 공간 복잡도는 O(M)이됩니다. 그러나지도에서 수행하는 경우 시간 복잡도는 O(N*logN)이고 공백은 O(N)입니다.

TreeMap의 질서 모든 요소를 ​​유지 : 우리가 예를 M에 대한 몇 가지 경우에 우선 순위 큐를 사용해야하면서는 약 엄지의 10

Answer 5

규칙 같은 단지 상수 아주 기본입니다. (그래서 직관적으로, 그것을 구축하는 데 시간이 걸립니다)

만 최소 또는 최대 격리. 덜 비싸지 만 덜 강력합니다.

Answer 6

두 가지 차이점이 있습니다 (이 질문은이 질문의 중복으로 간주되므로 Difference between PriorityQueue and TreeSet in Java?과 더 관련이 있습니다).

(1) PriorityQueue는 TreeSet에서 dup을 가질 수없는 곳에서 중복을 가질 수 있습니다. 따라서 Treeset에서 비교 자 (comparator)가 2 개의 원소를 같은 것으로 간주하면 TreeSet은 그 2 개의 원소 중 하나만 유지하고 다른 하나는 버립니다.

(2) TreeSet 반복자는 정렬 된 순서로 컬렉션을 트래버스하지만, PriorityQueue 반복자는 정렬 된 순서로 트래버스하지 않습니다. PriorityQueue의 경우 정렬 된 순서로 항목을 가져 오려면 remove()를 반복적으로 호출하여 대기열을 삭제해야합니다.

이러한 데이터 구조에 대한 Java의 구현에 대한 논의가 제한적이라고 가정합니다.

Answer 7

모두는 당신이 달성하기를 원하는 것에 달려 있습니다. 다른 것을 선택하기 전에 고려해야 할 요점은 다음과 같습니다.

1. PriorityQueue TreeMap이 중복되지 않도록 (즉, 동일한 우선 순위로) 허용합니다.
2. TreeMap의 노드에있는 동안
3. PriorityQueue 인은 배열을 기반으로 (이 레드 블랙 트리에 기반으로) TreeMap의의는 O (logn) 인 반면 PriorityQueue 인의 복잡성, O (N) (때 크기를 증가)입니다 서로 링크되어 있으므로 TreeMap이 O (logn) 시간이 소요되는 동안 PriorityQueue 메소드에 O (n) 시간이 소요됩니다.