최단 경로를 찾을 때 널리 사용하는 다익스트라 알고리즘은, 탐색 큐의 자료구조가 전체 성능에 결정적인 영향을 미친다. 때문에 추가/삭제를 빠르게 수행할 수 있는 우선순위 큐를 주로 사용한다.
우선순위 큐는 일반 큐와 비슷하지만, 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 출력된다는 점이 다르다. 우선순위 큐는 크게 배열, 연결리스트, 힙 이렇게 세 가지 방법으로 구현할 수 있다. 그중 완전 이진 트리 구조를 갖는 힙으로 구현하면 추가/제거의 효율성이 크게 향상된다.
| 구현 방법 | 삽입 | 삭제 |
|---|---|---|
| 순서없는 배열 | O(1) | O(n) |
| 순서없는 연결리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결리스트 | O(n) | O(1) |
| 힙 | O(log n) | O(log n) |
이진 트리는 각 부모 노드가 왼쪽/오른쪽 최대 2개의 자식 노드를 가질 수 있는 구조를 가리킨다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨을 완전히 채워진 상태로 유지해야 한다. 때문에 자식 노드를 추가할 땐 왼쪽부터 차례대로 채워야 한다. 아래 이미지 왼쪽에 있는 트리는 31번 노드의 자식을 오른쪽부터 채웠기 때문에 완전 이진 트리가 아니다.
힙은 크게 최대 힙(Max Heap), 최소 힙(Min Heap)으로 분류된다. 최대 힙은 부모 노드가 항상 자식 보다 크거나 같고, 최소 힙은 부모 노드가 항상 자식보다 작거나 같다. 다익스트라 알고리즘은 거리 값이 낮은 노드에 높은 우선순위를 부여하므로, 루트 노드가 가장 짧은 거리 값(우선순위가 높은)을 갖는 최소 힙을 사용하는 것이 적절하다.
위에서 살펴본 완전 이진 트리 특성을 이용하면 각 노드의 인덱스를 아래 공식으로 계산할 수 있다.
예를들어 부모 노드의 인덱스가 2라면 왼쪽 자식 인덱스는 5, 오른쪽 자식 인덱스는 6이 된다. 이처럼 한 노드의 인덱스만 알면 해당 노드의 부모/자식 노드의 인덱스도 확인할 수 있어서 배열 구조로도 트리를 표현할 수 있다.
노드 추가는 최소 힙 속성(부모 노드 ≤ 자식 노드)을 만족할 때까지 부모 노드와 비교하며 위치를 교환하는 방식으로 이뤄진다. 노드 위치를 교환하는 과정은 heapify-up이라고 부른다. heapify-up은 최악의 경우 트리 높이 만큼 반복되고, 트리 높이는 $\log_{2}V$이므로 노드 추가의 시간 복잡도 역시 $\log_{2}V$를 갖는다.
heap.push(node)<aside> <img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> 트리에서 높이는 루트 노드(깊이 0)에서 리프 노드까지의 거리를 의미한다. 완전 이진 트리에서 각 레벨의 노드 수는 이전 레벨 노드 수의 2배로 증가한다. 따라서 높이가 $h$인 완전 이진 트리는 최소 $2^{h}$에서 최대 $2^{h+1}-1$개의 노드를 가질 수 있다. 예를 들어, 높이가 2인 트리는 최대 $2^{2+1}-1=7$개의 노드를 가질 수 있다. 즉, $V$개의 노드를 가진 완전 이진 트리의 높이는 $\log_2(V)$로 계산할 수 있다.
</aside>