우선순위큐(Priority Queue)

오늘은 다익스트라 문제를 본격적으로 풀어보기 전에 먼저 그래프 문제에서 자주 사용하는 우선순위 큐라는 자료구조에 대해 정리를 해보겠다. 

결국에 큐이기 때문에 add, poll, peek 등의 연산을 수행하지만, 하는 일과 내부 구조는 기존의 큐와 완전히 다르다. poll이나 peek의 연산으로 추출되는 원소는 기존 큐의 연산순서인 FIFO에 따라서 제일 먼저 들어온 요소가 나오는 것이 아니라, 말 그대로 현재 큐 안에서 제일 우선순위가 높은 요소가 먼저 나온다. 

이는 우선순위 큐가 기존 알던 큐가 아닌 힙(heap)이라는 자료구조로 구현되기 때문에 가능하다. 

가장 많이 사용하는 형태는 클수록 우선순위가 높은 형태 or 작을수록 우선순위가 높은 형태이다.

어떤 우선순위 큐의 front에 위치하는 원소가 가장 큰 수, 즉 가장 먼저 나오는 형태의 우선순위 큐를 최대 힙, 반대의 경우를 최소 힙이라고도 한다. 

• 최대힙(default) : poll연산을 했을 때, 제거되는 원소는 큐에 들어 있던 원소 중에서 가장 큰 원소이다. 
• 최소힙 : poll연산을 했을 때, 제거되는 원소는 큐에 들어 있던 원소 중에서 가장 작은 원소이다.   

 

그렇다면 힙이라는 자료구조에 대해 알아보자. 완전 이진 트리의 구조를 가진다. 완전 이진트리란 모든 노드가 2개의 자식을 가지려는 성질이 있는 트리이다. 따라서 우선순위 큐의 로직을 이해하기 위해서는 힙을 구성하는 완전 이진트리의 삽입&삭제 연산을 이해하면 된다. 자바에서는 Collection에서 Queue인터페이스를 구현한 PriorityQueue라는 클래스가 정의되어 있다. 오늘은 삽입 삭제 연산만을 정리하고, 직접 큐를 구현하는 것은 다음에 글을 수정하면서 추가하도록 하겠다. 

힙은 배열을 사용해서 구현한다. 힙을 구현한다는 것은 완전 이진트리를 구현한다는 의미도 되겠다. 단, 배열의 인덱스는 0이 아니라 1부터 시작한다. 아래의 이미지로 예를 들면 루트 노드부터 순서대로 arr[1] = 15, arr[2] = 12, arr[3] = 7 , .... , arr[12] = 1이 된다.

위와 같이 배열의 인덱스를 매기면 현재 노드(k)에서 부모노드, 왼쪽 자식노드, 오른쪽 자식 노드로의 접근이 매우 빠르다. 이러한 첨자의 접근이 가능한 것은 완전 이진트리라는 보장이 되어 있기 때문이다.

• 부모노드의 인덱스 : k / 2(몫 연산자)
• 왼쪽자식노드의 인덱스 : k * 2
• 오른쪽자식노드의 인덱스 : k * 2 + 1 

우선 순위큐를 직접적으로 사용하는 다익스트라 문제 풀이에서 우선순위 큐를 적용하는 방법을 정리하겠다.

완전 트리에서 삽입 삭제 연산을 최대힙을 예시로 들어서 이미지와 함께 정리하겠다. 한 가지 짚고 넘어 가야 하는 중요한 성질이 있는데 모든 정점은 자신의 자식들보다 우선순위가 높다. 우선순위가 높다는 말은 다양한 데, 지금은 최대 힙을 예시로 들었기 때문에 이 예시에서 우선순위가 높다는 말은 모든 정점은 자신의 자식들보다 값이 크다는 말이다.

[ 완전 이진 트리의 삽입 ]

1. 새로운 숫자 9를 추가해보자 .

새로운 숫자가 들어오면 완전이진트리는 형태를 유지하는 성질을 지키기 위해 그를 만족할 수 있는 첫 빈자리, 즉 위의 그림 상에서는 3의 자식, 1과는 형제인 노드로 삽입이 된다.

2. 9를 우선순위에 맞는 위치로 이동시킨다. 

• 자신의 부모인 3보다 자신의 값이 더 크다. 자식의 우선순위가 부모보다 높은 상태이기 때문에, 힙의 조건(최대힙)을 유지하기 위해 3과 9의 위치를 바꾼다. 
• 위치를 바꾸고 나서도, 자신의 부모인 7보다 자신의 값이 더 크다. 자식의 우선순위가 부모보다 높은 상태이기 때문에, 힙의 조건(최대힙)을 유지하기 위해 7과 9의 위치를 바꾼다.
• 루트 노드는 9보다 크기 때문에 이제는 9가 자신의 위치를 찾았기 때문에 이동을 종료한다. 
  • 물론 새로 들어온 수가 루트보다 크다면 루트의 자리를 빼앗아 올 수 있다.
• 힙은 완전 이진 트리의 형태이기 때문에, 반드시 균형 트리이며, 원소의 개수가 n일때, 자리 바꾸기의 최대 횟수는 트리의 최대 높이(리프노드~루프노드) 즉, logN만큼 수행하기 때문에 O(logN)의 시간복잡도를 가진다.

약간 헷갈릴 수도 있는 분들을 위해 말을 하자면 9와 7이 자리를 바꿀 때, 4와도 비교는 해야 하는 것 아닌가? 하는 궁금증이 생길 수도 있다. 필자도 처음엔 그랬다. 하지만 생각해보면 단순하게 해결된다. 

예를 들어 A가 B라는 자식 노드 1개가 있었다고 해보자. 이때 C가 새로 삽입되었다. 이 경우 새로 들어온 C와 A를 비교하기도 전에 자명한 사실은 A > B라는 것이다. 그렇기 때문에 최대힙 우선순위를 유지하기 위해 B가 A의 자식으로 있었지 않았겠는가? 

그런데 위의 경우에서 만약 C > A라면, 두 노드의 위치를 바꾼다. 이때, 위의 부등호식을 그대로 내려와 연결해보면 C > A > B이다. 결국 C가 A보다 크다면 B보다는 당연히 큰 결과인 것이다.

 

[ 완전 이진 트리의 삭제 ] O(logN)

1. 루트 노드의 값을 삭제한다.

여기까지 오느라 잠시 잊고 있었을 내용을 다시 상기시키고 넘어가겠다. 우린 지금 우선순위큐를 공부하고 있었는데, 우선순위 큐는 힙으로 구현되고 이러한 힙은 완전 이진트리로 구현된다고 했다. 그렇다면 이 예시의 경우 최대힙에서 삭제연산(poll)이 발생하면 당연히 우선순위가 가장 높은 -> 루트 노드가 삭제된다. 

2. 가장 끝에 있는, 배열의 끝값을 루트에 앉힌다.

묻지도 따지지도 않고, 그냥 바로 가장 끝에 있는 노드를 루트에 저장하고, 여기서 부터 우선순위를 유지하기 위해 삽입과는 반대로 자식과의 크기 비교를 한다. 

이때, 주의해야 할 점은, 현재 나의 자식들 중 하나만 나보다 크다면 해당 노드와 자리를 바꾸면 되지만, 두 개의 자식 노드가 모두 나보다 크다면 두 자식 중 더 큰 노드와 자리를 바꾸어야 계속적으로 힙의 조건(우선순위)을 유지할 수 있다. 

3. 12와 자리를 바꾼다.

자식 노드 12, 9가 모두 3보다 크지만 둘 중에 더 큰 12와 자리를 바꾼다. (12 > 9이므로 우선순위 유지된다.)

3. 11과 자리를 바꾼다.

자식 노드 11, 9가 모두 3보다 크지만 둘 중에 더 큰 11과 자리를 바꾼다. (11 > 9이므로 우선순위 유지된다.)

4. 10과 자리를 바꾼다.

자식 노드 10, 4가 모두 3보다 크지만 둘 중에 더 큰 10과 자리를 바꾼다. (10 > 4이므로 우선순위 유지된다.)

 

힙과 이진 탐색 트리의 차이점

힙	이진 탐색 트리
데이터 중복 가능	데이터 중복 불가