💚 자료구조 - 우선순위 큐의 시간복잡도는 어떻게 되며 그 이유는 무엇인지 설명해 보시오.

우선순위 큐(Priority Queue)

우선순위 큐는 우선순위가 가장 높은 요소가 먼저 처리되는 자료구조로, 주로 힙(Heap)을 사용해 구현됨.

즉, 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말함.

주요 동작

• insert

• delete

• peek() : 우선순위 큐에서 최대 우선순위 값을 반환함. 최대 우선순위 값(최대 힙)은 항상 루트에 있으므로 루트 값을 반환함.

4 -> 8 -> 2 순으로 데이터가 들어간다고 할 때, 우선순위 큐의 처리 순서는 다음과 같다. (높은 값이 높은 우선순위를 갖는다고 가정)

input : 4 -> 8 -> 2 queue : 4 -> 8 -> 2 priority queue : 8 -> 4 -> 2

구현

구현 방법	enqueue()	dequeue()
배열 (unsorted array)	O(1)	O(N)
연결 리스트 (unsorted linked list)	O(1)	O(N)
정렬된 배열 (sorted array)	O(N)	O(1)
정렬된 연결 리스트 (sorted linked list)	O(N)	O(1)
힙 (heap)	O(logN)	O(logN)

• 힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙을 가지고 구현을 한다.

// 낮은 수가 우선순위를 가짐 
PriorityQueue<Integer> pq =  new  PriorityQueue<>();  
// 높은 수가 우선순위를 가짐 
PriorityQueue<Integer> pq =  new  PriorityQueue<>(Collections.reverseOrder());  
// 사전 순으로 더 빨리오는 문자열이 우선순위를 가짐 
PriorityQueue<String> pq =  new  PriorityQueue<>();

힙(Heap)

힙은 완전 이진 트리(Complete Binary Tree) 형태로 구현되며, 노드들은 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 기반으로 우선순위가 정해진다.

• 트리(tree) : 부모-자녀처럼 계층적인 형태를 가지는 구조

• 이진 트리(binary tree) : 자녀가 최대 두 개인 트리

• max heap : 부모 노드의 키(key)가 자식 노드의 키(key)보다 크거나 같은 트리

• min heap : 부모 노드의 키(key)가 자식 노드의 키(key)보다 작거나 같은 트리

주요 동작

• insert

• delete

• peek

정리

우선순위 큐(Priority Queue)는 우선순위가 가장 높은 요소가 먼저 처리되는 자료구조이다. 일반적으로 힙(Heap)을 사용하여 구현되며, 우선순위 큐의 삽입(insert)과 삭제(delete) 연산은 모두 O(log n)의 시간복잡도를 가진다.

힙(Heap)은 완전 이진 트리(Complete Binary Tree)를 기반으로 하며, 이진 트리는 각 노드가 자식 노드보다 우선순위가 높거나 같은 속성을 유지한다.

최대 힙(Max Heap)에서는 부모 노드의 키가 자식 노드들의 키보다 크거나 같고, 최소 힙(Min Heap)에서는 부모 노드의 키가 자식 노드들의 키보다 작거나 같다. 이러한 특성으로 힙은 삽입 및 삭제 연산을 효율적으로 처리할 수 있다.

• 삽입 연산 (insert): 새로운 원소를 힙에 추가할 때, 힙의 마지막 노드에 원소를 삽입하고, 해당 원소를 적절한 위치로 “힙 정렬”하면서 이동시킨다. 이 과정에서 트리의 높이에 비례하여 비교와 교환이 일어나므로 시간복잡도는 O(log n)이다.

• 삭제 연산 (delete): 우선순위 큐에서 우선순위가 가장 높은 원소(최상위 원소, 루트)를 삭제할 때는, 루트 원소를 삭제하고 마지막 원소를 루트로 올린 뒤, 해당 원소를 적절한 위치로 “힙 정렬”한다. 이 과정에서도 비교와 교환이 일어나므로 시간복잡도는 O(log n)이다.

• peek 연산: 우선순위 큐에서 우선순위가 가장 높은 값을 확인하는 연산은 O(1)이다. 이는 루트 노드의 값을 바로 반환하기 때문이다.

따라서, 우선순위 큐는 힙을 사용하여 구현하면 최악의 경우에도 O(log n)의 시간복잡도를 보장하며, 효율적인 우선순위 기반 처리가 가능하다.