Min Heap 대 Priority queue의 일반 배열 구현

Question

Dijkstra의 우선 순위 큐를 최소 힙으로 구현하는 것이 가장 좋은 경우는 언제 일반 배열을 사용하는 것이 더 좋습니까?

하나는 실행 시간이 O(V^2 + E)이고 다른 하나는 O((V+E)logV)입니다. V< E, O(V^2 + E)= O(E^2) 및 O((V+E)logV) = O(ElogV) 그래서 힙 구현이 보인다 때 E< V 다음 O(V^2+E) = O(V^2)는 그것이 더 이상 O((V+E)logV)=O(2VlogV)=O(VlogV)

때 다시 더 좋을 수 있습니다.

또한 공간 복잡성도 동일합니다. 즉 O(n)입니다.

Dijkstra 's에서 최소 우선 순위 큐의 간단한 배열 구현이 더 좋지만 대소 문자를 생각할 수없는 경우가 있다고 가정합니다.

Answer 1

@JimMischel이 말하는 Dijkstra의 경우, 어떤 예도 생각할 수 없으며, 존재하지 않는다고 생각합니다. 그러나 모든 노드에 대한 최단 경로가 아닌 단일 마무리 노드에 대한 최단 경로 하나를 찾는 데 중점을 둔 UCS (Uniform Cost Search)의 경우를 생각해 볼 수 있습니다. 이것은 국가 간 전환이 일정한 문제와 관련이 있습니다.

예를 들어 15 개의 퍼즐을 풀고 있습니다 (모든 전환에는 비용이 1입니다). 더욱이 이런 종류의 문제에서 솔루션 비용의 범위는 잘 알려져 있으므로 각 비용에 대해 이러한 비용의 간단한 경로 벡터를 저장할 수있는 상태 배열을 탐색 할 수 있습니다. 이 경우, 모든 연산은 O(1)이고 이진 최소 힙보다 배열을 사용하는 것이 더 효율적입니다.