PriorityQueue란?
PriorityQueue는 원소들을 우선순위에 따라 저장하고 관리하는 자료구조이다. 각각의 원소는 우선순위의 순서대로 저장된다.
PriorityQueue는 일반적으로 min-heap 이나 max-heap을 사용해 구현된다. Heap은 트리 형태의 우선순위대로 순서가 나타내지는 자료 구조로. min-heap 방식으로 구현되면 우선순위가 낮은 요소가 맨 앞에 오고, 우선순위가 높은 요소가 맨 뒤에 오게 되며, max-heap 방식을 사용해 구현되면, 우선순위가 높은 요소가 맨 앞으로 오고 우선순위가 낮은 요소가 맨 뒤에 위치한다.
Kotlin과 Java의 PriorityQueue는 min-heap 방식으로 구현되어 우선순위가 낮은 요소가 가장 앞쪽에 온다. 예를 들어 아래와 같이 12, 14, 13을 순서대로 입력할 경우 우선순위가 낮은 12가 맨 앞으로 오고 우선순위가 높은 14가 맨 뒤로 간다.
val priorityQueue = PriorityQueue<Int>()
priorityQueue.offer(12) // [12]
priorityQueue.offer(14) // [12, 14]
priorityQueue.offer(13) // [12, 13, 14]
PriorityQueue의 시간 복잡도
PriorityQueue는 Queue이기 때문에 얼핏 보기에는 우선순위에 따라 Linear하게 구성되는 것처럼 보이지만, 내부적으로는 데이터를 저장하기 위해 우선순위에 따라 Tree 자료 구조를 가진다.
예를 들어 11, 12, 13, 14, 15를 순서대로 PriorityQueue에 넣으면 아래와 같은 형태가 된다.
val priorityQueue = PriorityQueue<Int>()
priorityQueue.offer(11) // [11]
priorityQueue.offer(12) // [11, 12]
priorityQueue.offer(13) // [11, 12, 13]
priorityQueue.offer(14) // [11, 12, 13, 14]
priorityQueue.offer(15) // [11, 12, 13, 14, 15]
원소를 삽입하기 위한 시간 복잡도
Heap 구조는 완전 이진트리로 구성되며, 부모 노드의 우선순위는 자식 노드의 우선순위보다 높은 특성을 가진다. 원소를 추가할 때는 새로운 원소를 우선순위 큐의 가장 마지막에 추가한 후 우선 순위에 따라 재배치하는 과정을 거친다. 이 때문에 삽입을 위한 시간 복잡도는 O(logN)이 된다.
원소를 우선 순위가 가장 높은 원소를 가져오고 삭제하기 위한 시간 복잡도
원소를 Queue에서 빼기 위한 시간 복잡도는 맨 앞의 원소를 가져오면 되기 때문에 O(1)이 된다.
특정 원소를 탐색을 위한 시간 복잡도
Priority Queue에서 특정 원소를 찾기 위해서는 전체 노드를 우선순위에 따라 반복적으로 확인해야 한다. 이 때문에, O(N)의 시간 복잡도를 가진다.
Heap에서 원소를 추가할 때는 바로 위의 부모 노드와만 비교해서 위로 옮길지 말지가 결정되기 때문에 Tree의 Depth에 해당하는 시간 복잡도인 O(logN)을 가지지만, 원소 탐색 시에는 Tree의 Depth가 크기를 나누는데 영향이 없기 때문에 모든 노드를 탐색해야 하기 때문이다.
예를 들어 아래와 같은 Min-Heap 구조에서 위에서 맨 왼쪽 3번째에 있는 11은 위에서 맨 오른쪽 2번째에 있는 12보다 작은 것을 확인할 수 있다.
특정 원소 삭제를 위한 시간 복잡도
특정 원소를 탐색하기 위한 시간 복잡도는 O(N)이고, 특정 원소 삭제를 위해서는 우선적으로 탐색 수행되어야 하므로 O(n)이 된다.
