우선순위 큐 (Priority Queue)의 개념 및 구현

우선순위 큐(Priority Queue)는 각 요소에 우선순위가 부여되어, 우선순위가 높은 요소가 먼저 처리되는 자료구조입니다. 일반 큐(Queue)와 달리, 데이터의 처리 순서가 요소의 우선순위에 따라 결정되므로 효율적인 데이터 관리와 처리가 필요한 알고리즘에서 널리 사용됩니다.

---

1. 우선순위 큐란?

우선순위 큐는 FIFO(First In, First Out) 큐의 변형으로, 각 요소가 우선순위(priority)를 가지며, 우선순위가 높은 요소가 가장 먼저 삭제됩니다. 우선순위 큐는 여러 방식으로 구현될 수 있으며, 최대 힙(Max Heap) 또는 최소 힙(Min Heap) 구조가 자주 활용됩니다. 일반적으로 사용되는 두 가지 우선순위 큐 유형은 다음과 같습니다.

• 최대 우선순위 큐: 우선순위가 높은(큰) 요소가 먼저 나갑니다.
• 최소 우선순위 큐: 우선순위가 낮은(작은) 요소가 먼저 나갑니다.

---

2. 우선순위 큐의 주요 연산

우선순위 큐는 다음과 같은 기본 연산을 지원합니다.

• Enqueue (삽입): 큐에 요소를 우선순위와 함께 추가합니다.
• Dequeue (삭제): 큐에서 우선순위가 가장 높은 요소를 제거합니다.
• Peek: 현재 큐에서 가장 높은 우선순위의 요소를 확인하되 제거하지 않습니다.

이러한 연산은 각 요소의 우선순위를 기준으로 처리되어야 하므로, 힙을 통해 효율적으로 관리됩니다.

---

3. 우선순위 큐의 활용 사례

우선순위 큐는 다양한 상황에서 유용하게 사용됩니다.

1. 운영체제의 프로세스 스케줄링: CPU는 우선순위에 따라 프로세스를 처리합니다.
2. 네트워크 패킷 스케줄링: 중요도가 높은 패킷을 먼저 전송하거나 처리합니다.
3. 다익스트라 알고리즘: 그래프의 최단 경로 탐색에서 다음 노드를 선택할 때 사용됩니다.
4. 이벤트 관리: 특정 조건에서 우선순위가 높은 이벤트를 먼저 처리합니다.

---

4. 우선순위 큐의 구현 (C# 예제)

우선순위 큐는 배열이나 연결 리스트로 구현할 수 있지만, 힙을 사용하면 삽입과 삭제 연산이 O(log N)의 시간 복잡도를 가지며 효율적입니다. 여기에서는 최소 힙(Min Heap) 기반의 우선순위 큐를 구현해 보겠습니다.

4.1 우선순위 큐 클래스 구현

C#에서 List<T>를 사용해 간단한 최소 힙 기반의 우선순위 큐를 작성할 수 있습니다.

using System;
using System.Collections.Generic;

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> heap = new List<T>();

    // 요소 추가
    public void Enqueue(T item)
    {
        heap.Add(item);
        int i = heap.Count - 1;

        // 새 요소를 힙에 맞는 위치로 올림
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (heap[i].CompareTo(heap[parent]) >= 0) break;
            Swap(i, parent);
            i = parent;
        }
    }

    // 우선순위가 가장 높은 요소 삭제
    public T Dequeue()
    {
        if (IsEmpty())
            throw new InvalidOperationException("Queue is empty");

        T result = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);

        int i = 0;

        // 새 루트 요소를 힙에 맞는 위치로 내림
        while (i < heap.Count)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left >= heap.Count) break;

            int minIndex = (right < heap.Count && heap[right].CompareTo(heap[left]) < 0) ? right : left;

            if (heap[i].CompareTo(heap[minIndex]) <= 0) break;

            Swap(i, minIndex);
            i = minIndex;
        }

        return result;
    }

    // Peek: 가장 높은 우선순위 요소 반환
    public T Peek()
    {
        if (IsEmpty())
            throw new InvalidOperationException("Queue is empty");
        return heap[0];
    }

    public bool IsEmpty()
    {
        return heap.Count == 0;
    }

    // Swap: 두 인덱스 위치의 요소를 바꿈
    private void Swap(int i, int j)
    {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

4.2 우선순위 큐 사용 예시

위에서 구현한 PriorityQueue 클래스를 사용해 데이터를 우선순위에 따라 삽입 및 삭제하는 예제입니다.

public class Program
{
    public static void Main()
    {
        PriorityQueue<int> pq = new PriorityQueue<int>();
        
        pq.Enqueue(10);
        pq.Enqueue(5);
        pq.Enqueue(20);
        pq.Enqueue(3);

        Console.WriteLine("Peek: " + pq.Peek()); // 가장 낮은 값 3 출력

        while (!pq.IsEmpty())
        {
            Console.WriteLine("Dequeue: " + pq.Dequeue());
        }
    }
}

코드 설명

• Enqueue: 힙의 마지막에 요소를 추가하고, 부모 노드와 비교하여 힙 조건을 유지합니다.
• Dequeue: 루트 요소(가장 높은 우선순위 요소)를 제거하고, 가장 마지막 요소를 루트로 올린 후, 자식 노드와 비교하며 위치를 조정합니다.
• Peek: 현재 우선순위가 가장 높은 요소를 반환하지만 큐에서 제거하지 않습니다.

---

5. 우선순위 큐의 장점과 단점

장점

• 효율적인 데이터 처리: 우선순위에 따라 중요한 요소를 빠르게 처리합니다.
• O(log N) 시간 복잡도: 힙을 사용하여 효율적인 삽입과 삭제가 가능합니다.

단점

• 정렬된 순서가 보장되지 않음: 힙을 사용해 정렬이 아닌 우선순위 조건만 유지하므로, 정렬된 데이터를 반환하는 것이 아닙니다.
• 메모리 사용: 각 요소의 우선순위를 유지하기 위해 추가 메모리 공간이 필요할 수 있습니다.

---

우선순위 큐는 우선순위에 따라 데이터를 처리하는 큐의 변형된 자료구조로, 운영체제의 스케줄링, 네트워크 패킷 관리, 다익스트라 알고리즘 등 다양한 분야에서 유용하게 활용됩니다.