2024-05-17-18. Priority Queue
Priority Queue (우선순위 큐)
내부 원소들에 우선순위가 있는 큐이다.
일반적인 큐는 가장 먼저 큐에 들어온 원소가 가장 먼저 나가는 반면, 우선순위 큐에서는 우선순위가 가장 높은 원소가 가장 먼저 나온다.
Priority Queue의 최단 연산 시간
우선 순위 큐의 삽입과 삭제 연산 시간의 합은 O(logn)보다 빠를 수 없다.
정렬에 걸리는 시간은 O(nlogn)보다 빠를 수 없다는 것이 알려져 있는데, 이를 이용하면 증명 가능하다.
우선 순위 큐를 사용하여 정렬을 하는 것이 가능하다. 원소를 전부 우선 순위 큐에 Insert하고, 먼저 Delete되는 것부터 순서대로 나열하면, 우선순위대로 정렬이 완료된다.
그런데 우선 순위 큐의 Insert, Delete가 O(logn)보다 적게 걸린다면, 위 과정에서 Insert, Delete를 n번 반복하므로, 정렬하는 데 O(nlogn) 보다 적게 걸리게 되는 모순이 발생한다.
Priority Queue의 구현 방법은?
- 정렬된 배열
- 배열을 우선순위가 낮은 원소부터 높은 원소 순으로 정렬한다.
- 삭제는 끝부분의 원소 하나를 빼면 되므로 빠르다.
- 그러나 우선순위가 낮은 원소가 삽입되면 그보다 우선순위가 높은 원소를 뒤로 옮겨야 하므로 시간이 오래 걸린다.
- 정렬되지 않은 배열
- 삽입은 맨 뒤에 하면 되므로 빠르다.
- 그러나 삭제할 때 가장 우선순위가 높은 것을 선형 탐색으로 찾아야 하므로 오랜 시간이 걸린다.
Balanced BST를 이용한 구현
AVL 트리, 2-3트리, Red-Black 트리를 이용해 힙을 구현해 보자.
- 트리가 우선순위대로 정렬되도록 하자. 즉 각 노드의 왼쪽 서브트리엔 부모 노드보다 우선순위가 높은 키값들이 오고, 오른쪽 서브트리에는 우선순위가 낮은 키값들이 오도록 한다.
- AVL 트리, 2-3트리, Red-Black 트리를 이용하면 트리 높이가 O(logn)이므로, 삽입에 O(logn)이 걸린다.
- 또한 우선순위가 가장 높은 키를 찾으려면 left로만 끝까지 가면 된다. 따라서 삭제에도 O(logn)이 걸린다.
다른 구현의 필요성
위와 같이 균형 이진 탐색 트리를 이용해도 O(logn)시간에 작동하는 우선 순위 큐를 만들 수 있다.
그러나 Heap을 이용하여 구현하는 것이 더 효율적이다. Heap을 이용해도 빅오 표기법으로는 O(logn)으로 같은 시간이 걸리지만, 실제 수행 시간은 몇배 더 빠르다.
이는 BST는 전체를 정렬된 상태로 유지하는 반면, Priority Queue는 우선순위가 가장 높은 원소 하나만 알면 되기 때문이다.
그 외의 원소들은 우선순위가 가장 높은 원소가 delete되었을 때, 우선순위가 다음으로 높은 것을 빨리 찾을 수 있도록 대략적인 정렬만 되어 있어도 문제없다.
Heap은 완전한 정렬 대신 대략적인 정렬만 하면 되므로, 수행 시간이 더 빠르다.
Heap
세 가지 특수한 이진 트리가 있다.
- Full Binary Tree
- 모든 노드의 자식 개수가 두 개 또는 0개인 이진 트리이다.
- 자식이 1개인 노드는 없다.
- Perfect Binary Tree
- 완벽하게 가득 찬 이진 트리.
- 각 레벨마다 최대 개수의 노드가 존재한다.
- 즉 노드가 0개가 아닌 모든 레벨 n에 대해, 2n개의 노드가 존재한다.
- Complete Binary Tree
- 마지막 레벨 위까지는 Perfect Binary Tree와 같지만, 마지막 레벨의 노드는 다 안 차있을 수도 있다.
- 단, 마지막 레벨에서 노드가 왼쪽부터 채워진다.
Heap은 Complete Binary Tree로 구성된다.
또한 부모의 키값이 자식 노드의 키값보다 작아야 한다.
단, 왼쪽 자식과 오른쪽 자식의 대소 관계는 고려하지 않아도 된다.
Heap에서는 가장 작은 키가 루트 노드에 존재하게 된다.
두 번째로 작은 키값은 루트 노드의 자식 노드 중 하나에 있다.
또한 아래로 내려갈수록 키값이 커진다.
키값으로 우선순위를 저장하면, Heap을 통해 우선순위 큐를 구현할 수 있다.
배열을 이용한 Heap 구현
- 루트 노드는 인덱스 1에 저장된다.
- 인덱스 i 노드의 왼쪽 자식 노드는 인덱스 2i, 오른쪽 자식 노드는 인덱스 2i+1에 저장한다.
- 그러면 인덱스 i의 부모 노드는 인덱스 i/2 가 된다.
배열에서 사이에 빈칸을 두지 않고 왼쪽부터 채우면 Complete Binary Tree 가 된다.
Heap Insert
먼저 Complete Binary Tree가 유지되도록, 마지막 레벨의 가장 오른쪽 원소의 바로 오른쪽(배열로 구현한 경우, 배열의 마지막 원소 다음)에 노드를 삽입한다.
만약 삽입된 노드가 부모 노드보다 작다면, 부모와 위치를 바꾼다. (부모의 원래 있던 자식은 부모보다 크므로, 삽입된 것보다도 당연히 크다)
부모 노드가 삽입된 노드보다 작을 때까지, 부모 노드와 위치를 바꾸는 것을 반복하며 위로 올려보낸다. 이를 up-heap 과정이라고 한다.
Heap Delete
루트 노드를 delete하고, 마지막 레벨의 끝에 있는 원소를 루트로 옮긴다.
옮겨진 노드의 자식 중 자신보다 작은 것이 있다면, 두 자식 중 더 작은 것과 위치를 바꾼다.
두 자식이 둘다 자신보다 클 때까지, 이러한 과정을 반복하며 노드를 아래쪽으로 옮긴다. 이를 down-heap 과정이라고 한다.