Priority Queue & Heap
이번엔 본격적으로 우선 순위 큐에 대해 알아보겠습니다. 우선 순위 큐란 힙이라는 구조를 활용하여 우선 순위가 있는 데이터를 다루기 위하여 고안된 특별한 데이터 구조입니다. 힙이란 Heap Property를 만족하는 특별한 트리의 형태를 말합니다. Heap Property란 다음 두 가지를 의미합니다.
- 완전 이진 트리(CBT, Complete Binary Tree)
- 각각의 부모 노드는 자식 노드보다 그 값이 같거나 클 것(Max Heap) 혹은 같거나 작을 것(Min Heap)
위와 같은 형태를 띠는 구조가 바로 힙, 우선 순위 큐입니다. 우선 순위 큐에서 수행할 수 있는 연산은 삽입(Insertion), 삭제(Deletion) 등이 있습니다. 먼저 삽입은 Shift-up 방식을 사용합니다. 트리의 제일 뒤에 원소가 삽입되면 부모 노드와 차례로 비교해 가며 해당 원소의 위치를 찾아가는 방식입니다. 다음으로 삭제는 Shift-down 방식을 사용합니다. 트리의 루트 노드를 삭제한 후 비어 있는 노드를 트리의 제일 마지막에 있는 노드로 대체합니다. 그 후 Heap Property를 만족하도록 바뀐 루트 노드의 값이 제자리를 찾아가는 방식입니다. 이 두 방식 모두 부모 노드와 차례로 비교해가기 때문에 최악의 경우 O(log(n))만큼의 시간이 걸리게 됩니다. (밑수는 2)
원소가 하나씩 주어지면서 우선 순위 큐를 만들 때를 살펴보겠습니다. n개의 원소가 차례대로 삽입이 되면 n-1번만큼의 삽입 연산이 수행됩니다. 즉 O(nlog(n))만큼의 시간이 걸리게 됩니다.
하지만 정말 모든 노드에 대해 삽입 연산을 해야할까요?
위 그림을 살펴보면, n개의 원소를 가진 우선 순위 큐에서 int(n / 2)만큼의 노드는 항상 부모 노드임을 알 수 있습니다. 즉 log(n)만큼의 연산을 n / 2번만 수행하면 됩니다.
즉 위와 같은 식이 얻어지고, 멱급수를 계산한 후 무한 급수를 구하면 다음과 같은 답이 얻어집니다.
다음은 파이썬으로 구현한 예제입니다.
결론적으로 우선 순위 큐를 만드는 방법은 Shift-up 또는 Shift-down 방식을 사용하는데, 이는 O(log(n))만큼의 시간 복잡도를 가집니다. 원래대로라면 n개의 원소에 대해 log(n)만큼의 연산을 수행하지만, 자세히 보니 모든 n개의 원소에 대해 연산을 수행할 필요가 없습니다. 그래서 실제로 값을 구해보니 O(n)의 시간 복잡도가 얻어짐을 알 수 있습니다. 이를 활용한 것이 힙 정렬(Heap Sort)입니다. 버블 정렬이나 삽입 정렬보다 더 빠른 시간 안에 수행되는 힙 정렬은 O(nlog(n))만큼의 시간 복잡도를 가집니다. 다음에 다뤄볼 기회가 있다면 다뤄보겠습니다.