2-7. 자료구조: 우선순위 큐

1. 우선순위 큐 (Priority Queue)의 이해

우선순위 큐는 자료구조의 한 종류로, 일반적인 큐와는 다르게 각 요소가 우선순위를 가지고 있다는 특징을 갖습니다. 큐에서 가장 먼저 들어온 요소가 먼저 나가는 FIFO (First-In, First-Out) 방식 대신, 우선순위가 가장 높은 요소가 먼저 큐에서 제거됩니다. 이는 마치 병원에서 응급 환자를 먼저 진료하는 것과 유사합니다.

1) 우선순위 큐의 특징

• 우선순위: 각 요소는 숫자나 다른 기준을 통해 부여되는 우선순위를 갖습니다. 이 우선순위는 큐 내에서 요소의 위치를 결정하는 데 사용됩니다.

• 연산: 주요 연산은 다음과 같습니다.

  • insert(element, priority): 요소와 해당 우선순위를 큐에 삽입합니다.
  • extract_max() 또는 extract_min(): (최대 우선순위 또는 최소 우선순위를 가진) 요소를 큐에서 제거하고 반환합니다.
  • peek() 또는 top(): 가장 높은 우선순위 (최대 또는 최소)를 가진 요소를 반환하지만, 큐에서 제거하지는 않습니다.
  • is_empty(): 큐가 비어 있는지 확인합니다.
  • 응용 분야: 스케줄링, 그래프 알고리즘 (Dijkstra, Prim), 이벤트 시뮬레이션 등 다양한 분야에서 활용됩니다.

2) 왜 우선순위 큐가 필요할까?

일반적인 큐나 스택으로는 우선순위를 고려한 데이터 관리가 어렵습니다. 예를 들어, 운영체제는 여러 프로세스에 CPU 시간을 할당해야 하는데, 이 때 각 프로세스의 우선순위에 따라 CPU 시간을 할당해야 합니다. 이런 경우 우선순위 큐를 사용하면, 우선순위가 높은 프로세스에 먼저 CPU 시간을 할당할 수 있습니다.

2. 힙 (Heap)을 이용한 우선순위 큐 구현

우선순위 큐는 다양한 방식으로 구현될 수 있지만, 일반적으로 효율적인 성능을 위해 힙(Heap) 자료구조를 사용합니다. 힙은 완전 이진 트리 형태를 가지며, 부모 노드는 자식 노드보다 (최대 힙의 경우) 크거나 (최소 힙의 경우) 작습니다.

1) 힙의 종류

• 최대 힙 (Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 힙입니다. 가장 큰 값은 루트 노드에 위치합니다.
• 최소 힙 (Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 힙입니다. 가장 작은 값은 루트 노드에 위치합니다.

2) 힙의 특징

• 완전 이진 트리: 힙은 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있습니다. 마지막 레벨은 왼쪽에서 오른쪽으로 채워집니다.
• 힙 속성: 최대 힙의 경우, 부모 노드의 값은 자식 노드의 값보다 크거나 같고, 최소 힙의 경우, 부모 노드의 값은 자식 노드의 값보다 작거나 같습니다.
• 효율적인 연산: 힙은 삽입, 삭제 연산을 $O(log n)$ 시간에 수행할 수 있으며, 최댓값/최솟값 검색은 $O(1)$ 시간에 수행할 수 있습니다.

3) 힙을 이용한 우선순위 큐 연산

• 삽입 (insert)

  1. 새로운 노드를 힙의 마지막 위치에 삽입합니다.
  2. 새로운 노드가 부모 노드보다 우선순위가 높으면, 부모 노드와 자리를 바꿉니다 (swap).
  3. 이 과정을 루트 노드까지 반복합니다 (heapify-up).

  

• 삭제 (extract_max / extract_min)

  1. 루트 노드를 제거합니다 (최대 또는 최소 우선순위 요소).
  2. 힙의 마지막 노드를 루트 노드로 이동시킵니다.
  3. 루트 노드가 자식 노드보다 우선순위가 낮으면, 자식 노드와 자리를 바꿉니다 (swap). (최대 힙에서는 가장 큰 자식, 최소 힙에서는 가장 작은 자식)
  4. 이 과정을 리프 노드까지 반복합니다 (heapify-down).

  

4) 파이썬 코드 예시 (최소 힙)

import heapq

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

    def is_empty(self):
        return len(self.heap) == 0

    def insert(self, element, priority):
        heapq.heappush(self.heap, (priority, element))

    def extract_min(self):
        if self.is_empty():
            return None
        return heapq.heappop(self.heap)[1] # 우선순위와 요소를 튜플로 저장

    def peek(self):
        if self.is_empty():
            return None
        return self.heap[0][1] # 우선순위가 가장 높은 요소 (최솟값) 반환

• heapq 모듈을 사용하여 힙을 구현합니다.
• insert 연산은 heapq.heappush()를 사용하여 요소를 힙에 추가합니다. 튜플 (priority, element) 형태로 저장하여 우선순위가 높은 순으로 정렬되도록 합니다.
• extract_min 연산은 heapq.heappop()를 사용하여 가장 우선순위가 높은 요소를 제거합니다.
• peek 연산은 self.heap[0]을 통해 가장 우선순위가 높은 요소를 확인합니다.

3. 우선순위 큐의 응용

우선순위 큐는 다양한 알고리즘과 문제 해결에 활용됩니다.

1) 다익스트라 (Dijkstra) 알고리즘

• 개념: 그래프에서 특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다.

• 활용: 각 노드까지의 현재까지의 최단 거리를 우선순위 큐에 저장합니다. 우선순위 큐에서 가장 짧은 거리를 가진 노드를 선택하고, 해당 노드를 기준으로 인접 노드까지의 거리를 갱신하며, 큐에 다시 삽입합니다.

  

2) 프림 (Prim) 알고리즘

• 개념: 그래프에서 최소 신장 트리 (Minimum Spanning Tree, MST)를 찾는 알고리즘입니다.

• 활용: 각 노드와 연결된 간선의 가중치를 우선순위 큐에 저장합니다. 우선순위 큐에서 가장 작은 가중치를 가진 간선을 선택하고, 해당 간선으로 연결된 노드를 MST에 추가합니다.

  

3) 스케줄링

• 개념: 작업의 우선순위에 따라 작업을 처리하는 방식입니다.
• 활용: 작업과 해당 작업의 우선순위를 우선순위 큐에 저장합니다. 큐에서 우선순위가 높은 작업을 먼저 처리합니다.

4) 힙 정렬 (Heap Sort)

• 개념: 힙 자료구조를 이용하여 배열을 정렬하는 알고리즘입니다.
• 활용: 정렬할 배열의 모든 요소를 힙에 삽입한 후, 힙에서 요소를 하나씩 제거하면서 정렬된 배열을 생성합니다.

5) CPU 스케줄링

• 개념: 여러 프로세스 중 어떤 프로세스를 먼저 실행할지 결정하는 방식입니다.
• 활용: 각 프로세스의 우선순위를 기준으로 우선순위 큐를 사용하여, 가장 우선순위가 높은 프로세스를 선택하여 CPU에 할당합니다.

4. 다양한 우선순위 큐 문제 예시

1) LeetCode 239. Sliding Window Maximum

• 문제: 주어진 배열 nums와 윈도우 크기 k에 대해, 각 윈도우에서 최댓값을 구하여 배열로 반환합니다.
• 해결 방법: 윈도우 내의 각 요소와 인덱스를 튜플로 하는 최대 힙 (Max Heap)을 사용합니다. 윈도우가 이동함에 따라 힙에서 벗어나는 요소를 제거하고, 새로운 요소를 추가합니다.

import heapq

def max_sliding_window(nums, k):
    """
    슬라이딩 윈도우 최대값을 구하는 함수

    Args:
        nums: 정수 배열
        k: 윈도우 크기

    Returns:
        각 윈도우의 최대값을 담은 배열
    """
    n = len(nums)
    if n * k <mark class="highlight"> 0:
        return []

    if k </mark> 1:
        return nums

    queue = []
    result = []
    for i in range(k):
        heapq.heappush(queue, (-nums[i], i))  # (값의 음수, 인덱스)

    result.append(-queue[0][0])

    for i in range(k, n):
        while queue and queue[0][1] <= i - k:  # 윈도우 밖의 인덱스 제거
            heapq.heappop(queue)
        heapq.heappush(queue, (-nums[i], i))
        result.append(-queue[0][0])  # 최대값

    return result

2) LeetCode 215. Kth Largest Element in an Array

• 문제: 정수 배열 nums에서 k번째로 큰 요소를 찾습니다.
• 해결 방법: 최소 힙 (Min Heap)을 사용합니다. 배열의 각 요소를 힙에 삽입하고, 힙의 크기가 k보다 커지면 힙에서 가장 작은 요소를 제거합니다. 최종적으로 힙의 루트 노드가 k번째로 큰 요소가 됩니다.

import heapq

def find_kth_largest(nums, k):
    """
    배열에서 k번째로 큰 요소를 찾는 함수

    Args:
        nums: 정수 배열
        k: k번째 큰 요소의 k

    Returns:
        k번째로 큰 요소
    """
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return min_heap[0]

5. 주의사항과 트러블 슈팅

1) 힙의 구현 오류

• 힙 속성 위반: 힙의 속성 (최대 힙 또는 최소 힙)을 올바르게 유지하지 못하면, 예상과 다른 결과가 발생합니다.
• 인덱스 오류: 힙의 삽입, 삭제 과정에서 인덱스 계산에 오류가 발생할 수 있습니다. 특히 자식 노드, 부모 노드의 인덱스 계산에 주의해야 합니다.
• 메모리 관리: 힙의 크기가 커지면 메모리 사용량이 증가할 수 있습니다. 필요에 따라 동적으로 메모리를 할당하고 해제해야 합니다.

2) 성능 문제

• 삽입/삭제 연산의 시간 복잡도: 힙의 삽입과 삭제 연산은 $O(log n)$ 시간이 소요됩니다. 힙의 크기가 커질수록 성능 저하가 발생할 수 있으므로, 연산 횟수를 최소화하는 방법을 고려해야 합니다.
• 힙의 균형: 힙이 불균형하게 구성되면, 일부 연산의 성능이 저하될 수 있습니다. 힙의 균형을 유지하기 위해 힙 재구성을 고려할 수 있습니다.

3) 엣지 케이스 처리

• 빈 큐: 큐가 비어있는 경우, extract_max 또는 extract_min 연산 시 예외 처리 (e.g., None 반환)를 해주어야 합니다.
• 중복된 우선순위: 동일한 우선순위를 가진 요소가 여러 개일 경우, 예상대로 동작하는지 확인해야 합니다. 파이썬 heapq 모듈에서는 먼저 들어온 요소가 먼저 나가는 FIFO 방식을 따릅니다.
• 자료형: 우선순위로 사용되는 자료형에 따라 비교 연산의 결과가 다를 수 있으므로, 적절한 비교 방법을 사용해야 합니다.

6. 결론

우선순위 큐는 효율적인 데이터 관리를 위한 강력한 도구이며, 특히 힙을 사용하여 구현할 경우 다양한 알고리즘과 문제 해결에 유용하게 활용될 수 있습니다. 힙의 특징, 연산 방법, 그리고 응용 분야를 이해하고, 다양한 문제 해결에 적용해 보세요.