Algorithm

[크래프톤 정글] 우선순위 큐

하루이2222 2024. 9. 20. 14:03

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지며, 우선순위에 따라 요소들이 정렬되어 처리되는 자료 구조이다. 우선순위 큐는 일반적인 큐(First-In-First-Out, FIFO)와는 다르게, 먼저 들어온 요소가 아니라 우선순위가 높은 요소가 먼저 처리된다. 이러한 특성 때문에 우선순위 큐는 다양한 실세계 응용에서 중요하게 사용된다.

우선순위 큐의 응용 예시

  • 응급실 환자 분류: 응급실에서는 환자가 도착한 순서가 아닌, 상태의 심각성에 따라 환자를 분류하고 치료 순서를 결정한다. 이때 우선순위 큐를 사용하여 심각한 환자를 먼저 처리할 수 있다.
  • 프로세스 스케줄링: 운영체제에서는 각 프로세스가 우선순위를 가지고 있으며, 우선순위가 높은 프로세스가 먼저 CPU를 할당받는다.
  • 네트워크 라우팅: 패킷의 중요도에 따라 전송 순서를 결정할 때 우선순위 큐를 사용할 수 있다.

우선순위 큐의 구현

우선순위 큐는 주로 힙(Heap) 자료 구조를 사용하여 구현된다. 힙은 특정 규칙에 따라 정렬된 완전 이진 트리로, 우선순위 큐의 효율적인 삽입과 삭제를 가능하게 한다. 힙에는 최대힙(Max Heap)과 최소힙(Min Heap)이 있으며, 우선순위 큐에서는 최대힙을 사용하는 경우가 많다.

1. 최대힙 (Max Heap)

  • 구조: 최대힙은 부모 노드가 자식 노드보다 항상 크거나 같은 값을 가지는 완전 이진 트리이다. 최대힙에서 루트 노드는 항상 트리의 최댓값을 가진다.
  • 연산: 최대힙에서는 가장 큰 값(루트 노드)을 O(1) 시간에 접근할 수 있으며, 새로운 요소의 삽입과 최대값의 제거는 O(log n) 시간에 수행된다.

2. 최소힙 (Min Heap)

  • 구조: 최소힙은 부모 노드가 자식 노드보다 항상 작거나 같은 값을 가지는 완전 이진 트리이다. 최소힙에서 루트 노드는 항상 트리의 최솟값을 가진다.
  • 연산: 최소힙에서는 가장 작은 값(루트 노드)을 O(1) 시간에 접근할 수 있으며, 새로운 요소의 삽입과 최솟값의 제거는 O(log n) 시간에 수행된다.

우선순위 큐의 주요 연산

  1. 삽입(Insert):

    • 새로운 요소를 우선순위 큐에 추가한다.
    • 힙의 규칙을 유지하기 위해 새로운 요소가 삽입된 후에 힙을 재구조화(Heapify)하여 부모 노드와 비교 및 스왑이 이루어진다.
    • 시간 복잡도: O(log n)

  2. Extract-Max(또는 Extract-Min):

    • 우선순위 큐에서 가장 높은 우선순위를 가진 요소(최대힙의 경우 최댓값)를 제거하고 반환한다.
    • 루트 노드(최댓값)를 제거한 후, 마지막 노드를 루트 위치로 이동시켜 힙 규칙을 유지하기 위해 다시 힙을 재구조화한다.
    • 시간 복잡도: O(log n)

  3. Peek:

    • 우선순위 큐에서 가장 높은 우선순위를 가진 요소를 반환하지만, 제거하지는 않는다.
    • 최대힙의 경우, 루트 노드에 접근하면 된다.
    • 시간 복잡도: O(1)

우선순위 큐의 구현 예제 (Python)

우선순위 큐는 Python의 heapq 모듈을 사용하여 최소힙으로 구현할 수 있다. 하지만 최대힙을 구현하기 위해서는 음수 값을 활용하는 방법이 일반적이다.

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        # 최대힙으로 사용하기 위해 음수 값을 넣는다.
        heapq.heappush(self.heap, -value)

    def extract_max(self):
        # 최대값을 추출 (원래 값으로 돌려놓기 위해 음수 값을 다시 음수로)
        return -heapq.heappop(self.heap)

    def peek(self):
        # 최대값을 반환 (heap[0]은 항상 최대값이 되도록 관리됨)
        return -self.heap[0]

# 사용 예시
pq = PriorityQueue()
pq.insert(10)
pq.insert(20)
pq.insert(15)
print(pq.peek())        # 20 출력
print(pq.extract_max()) # 20 출력
print(pq.extract_max()) # 15 출력

힙의 시간 복잡도 정리

  • 삽입(Insert): O(log n)

    • 힙에 요소를 추가한 후, 힙 규칙을 유지하기 위해 부모 노드와 비교하여 필요한 경우 스왑한다. 최악의 경우, 새로운 요소가 루트까지 올라가야 하므로, 트리의 높이에 비례하는 O(log n) 시간이 소요된다.

  • 최대값 또는 최소값 제거(Extract-Max/Min): O(log n)

    • 힙의 루트 노드(최댓값 또는 최솟값)를 제거한 후, 마지막 노드를 루트로 이동시켜 힙 규칙을 유지하기 위해 하향 힙 정렬(Heapify Down)을 수행한다. 이 과정은 트리의 높이에 비례하여 O(log n) 시간이 소요된다.

  • 최대값 또는 최소값 접근(Peek): O(1)

    • 힙의 루트 노드에 접근하는 연산은 O(1) 시간에 가능하다.

우선순위 큐의 장점

  • 효율적인 우선순위 처리: 다양한 응용 분야에서 중요한 요소를 우선 처리해야 할 때, 우선순위 큐는 매우 효율적이다.
  • 시간 복잡도: 힙을 이용한 우선순위 큐는 삽입과 삭제에 O(log n)의 시간 복잡도를 가지며, 이는 큐의 크기가 커져도 비교적 빠른 연산을 가능하게 한다.
  • 메모리 효율성: 힙을 사용하여 구현된 우선순위 큐는 완전 이진 트리의 특성을 이용하여 메모리를 효율적으로 사용할 수 있다.

우선순위 큐의 단점

  • 구현 복잡성: 기본 큐에 비해 구현이 더 복잡하며, 특히 힙의 재구조화 과정이 필요하다.
  • 특정 연산에 제약: 우선순위 큐는 삽입과 삭제가 효율적이지만, 일반적인 큐와 달리 중간에 있는 요소에 접근하는 것이 비효율적일 수 있다.

결론

우선순위 큐는 다양한 응용에서 중요한 요소를 빠르게 처리해야 하는 상황에서 매우 유용한 자료 구조다. 힙을 이용한 구현은 효율적이며, 다양한 문제 해결에 널리 사용된다. 특히, 응급실 환자 분류, 프로세스 스케줄링, 네트워크 패킷 처리 등 다양한 분야에서 우선순위 큐의 개념이 활용된다. 우선순위 큐의 구현과 그 시간 복잡도를 이해하는 것은 알고리즘 및 자료 구조 설계에서 중요한 부분을 차지한다.