[알고리즘] 우선순위 큐(Priority Queue)

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

 

 

1. 동작 원리

 일반적인 큐(Queue)가 입력된 순서대로 출력하는 선입선출(FIFO) 방식의 자료구조였다면, 우선순위 큐(Priority Queue)는 저장된 데이터 중 가장 우선순위가 높은 데이터를 우선적으로 출력하는 자료구조입니다. 이를 가능토록 하는 것이 힙 트리(Heap Tree) 입니다. 우선순위 큐는 내부적으로 데이터를 힙 트리 방식으로 저장하고, 출력 시 루트 노드를 제거하고 값을 반환함으로써 가장 큰(우선순위가 높은) 데이터를 출력하게 됩니다.

https://sam0308.tistory.com/73

[알고리즘] 트리(Tree)

 

 실제로 코드로 구현하기 위해서는 힙 트리에 존재하는 다음과 같은 규칙을 이용하면 됩니다.

 

- n번째 노드의 왼쪽 자식 : [(2 * n)+ 1]번째 노드

- n번째 노드의 왼쪽 자식 : [(2 * n)+ 2]번째 노드

- n번째 노드의 부모 : [(n - 1) / 2]번째 노드

 

 데이터를 배열이나 리스트의 형태로 저장한 뒤, 상기 규칙들을 이용하여 힙 트리의 구조를 유지하도록 하면 항상 루트 노드, 즉 0번째 원소가 최대값이 되므로 신속하게 최대값을 가져올 수 있습니다.

 

 

2. 구현(C#)

 다음은 우선순위 큐를 C#으로 구현한 예시입니다.

class PriorityQueue<T> where T : IComparable<T>
{
    T[] data;
    public int Count { get; private set; }
    public int Capacity { get; private set; }
    #region 생성자
    // 기본 생성자
    public PriorityQueue()
    {
        Count = 0;
        Capacity = 1;
        data = new T[Capacity];
    }
    // 초기 Capacity 지정 생성자
    public PriorityQueue(int capacity)
    {
        Count = 0;
        Capacity = capacity;
        data = new T[Capacity];
    }
    #endregion

    #region public function
    public void Enqueue(T value)
    {
        // data 배열이 꽉 찼다면 확장
        if (Count >= Capacity)
            Expand();
        // 데이터 추가
        data[Count] = value;
        Count++;

        // 힙 트리를 유지하기 위해 데이터 교환
        // 새로 추가한 노드부터 부모 노드와 비교하여 더 크다면 
        int now = Count - 1;
        while(now > 0)
        {
            int parent = (now - 1) / 2;
            // 부모 노드의 값이 더 크다면 정지
            if (data[now].CompareTo(data[parent]) < 0)
                break;

            // 값 교환
            T temp = data[now];
            data[now] = data[parent];
            data[parent] = temp;
            // 현재 위치 갱신
            now = parent;
        }

    }

    public T Dequeue()
    {
        // Count가 0이라면 예외 발생
        if (Count == 0)
            throw new IndexOutOfRangeException();

        // 루트 노드 값 추출
        // 마지막 노드와 교환 후 제거
        T result = data[0];
        data[0] = data[Count - 1];
        data[Count - 1] = default(T);
        Count--;

        // 힙 트리를 유지하도록 데이터 교환
        // 루트부터 시작하여 자식 노드 중 큰 쪽과 비교, 현재 노드가 더 작다면 교환
        int now = 0;
        while(now < Count)
        {
            int left = (now * 2) + 1;
            int right = (now * 2) + 2;

            int next = now;
            // 왼쪽 노드가 존재하고 값이 더 크다면 next 갱신 
            if (left < Count && data[next].CompareTo(data[left]) < 0)
                next = left;
            // 오른쪽 노드가 존재하고 값이 더 크다면 next 갱신 
            if (right < Count && data[next].CompareTo(data[right]) < 0)
                next = right;
            // 갱신되지 않았다면 루프 종료
            if (next == now)
                break;

            // 값 교환
            T temp = data[now];
            data[now] = data[next];
            data[next] = temp;
            // 현재 위치 갱신
            now = next;
        }

        return result;
    }

    public T Peek()
    {
        // Count가 0이라면 예외 발생
        if (Count == 0)
            throw new IndexOutOfRangeException();

        return data[0];
    }
    #endregion

    #region private function
    // data 배열 확장용
    // 기존 Capacity의 2배로 확장
    void Expand()
    {
        T[] newData = new T[Capacity * 2];
        for(int i = 0; i < Count; i++)
            newData[i] = data[i];

        data = newData;
        Capacity *= 2;
    }
    #endregion

 모든 데이터 타입에 대응할 수 있도록 제네릭(T)을 사용하였으며, 우선순위를 비교하기 위해 T는 IComparable 인터페이스를 상속받은 타입으로 제한하였습니다. 기존 큐에서 자주 쓰는 기능인 Enqueue(), Dequeue(), Peek()을 구현하였으며, 내부 데이터 구조는 배열 형태로 힙 트리를 유지하도록 했습니다. List와 마찬가지로 현재 배열의 최대 크기인 Capacity 값을 둔 뒤, 현재 Count가 Capacity 이상이라면 Expand() 함수를 통해 2배로 확장하도록 했습니다. 

 

 Enqueue()와 Dequeue()의 반복문 부분은 힙 트리에서 원소 추가, 제거 후의 과정을 코드로 작성한 것입니다. Enqueue()에서는 부모 노드가 배열의 (n - 1) / 2번째 원소임을 이용하여 값을 비교한 뒤, 부모보다 현재 노드의 값이 더 크다면 교환 후 이동하는 과정을 반복합니다. Dequeue()에서는 왼쪽 자식 노드가 (n * 2) + 1, 오른쪽 자식 노드가 (n * 2) + 2번째 원소임을 이용합니다. 다만 자식 노드가 존재하는지, 그리고 어느쪽이 더 큰 지 구분해야 하므로 먼저 왼쪽 자식 노드가 존재하는지 체크 후 비교, 이후 오른쪽 자식 노드가 존재하는지 체크 후 비교하는 과정을 추가하였습니다. Peek()은 단순하게 루트 노드(data[0])를 반환하도록 구현했습니다.

 

 다음은 위에서 구현한 우선순위 큐의 간단한 사용 예시입니다.

class Player : IComparable<Player>
{
    public int level;
    public Player(int lv)
    {
        level = lv;
    }

    public int CompareTo(Player other)
    {
        if (level == other.level)
            return 0;

        return level < other.level ? -1 : 1;
    }
}

static void Main(string[] args)
{
    PriorityQueue<Player> queue = new PriorityQueue<Player>();

    queue.Enqueue(new Player(25));
    queue.Enqueue(new Player(57));
    queue.Enqueue(new Player(41));
    queue.Enqueue(new Player(96));
    queue.Enqueue(new Player(33));

    // 부호를 원래대로 돌리고 출력
    while (queue.Count > 0)
        Console.WriteLine(queue.Dequeue().level);
}

사진 1. 우선순위 큐 예시

 IComparable 인터페이스를 상속받아 레벨을 기준으로 비교 가능하게 만든 Player 클래스를 선언한 뒤, 해당 타입의 우선순위 큐를 생성하였습니다. 무작위 레벨의 플레이어 데이터를 추가한 뒤 출력해보면 레벨이 높은 순서대로 출력되는 것을 확인할 수 있습니다. 이렇게 직접 클래스를 선언하여 사용할 경우, CompareTo()를 어떻게 구현하느냐에 따라 우선순위를 임의로 정할 수 있습니다. 위 예시의 경우 ComapreTo의 마지막 줄에서 -1과 1을 반대로 하면 레벨이 낮은 순서대로 출력하게 됩니다.

 

 참고로 숫자(numeric) 타입을 사용할 경우 부호를 반대로 입력하여 낮은 값이 우선적으로 출력되도록 할 수 있습니다. 예를 들어 int형 우선순위 큐에 -30, 20, -10, 40 을 넣었다면 40, 20, -10, -30 순으로 출력할 것입니다. 이 때 데이터 삽입 시 부호를 반대로 넣는다면 30, 10, -20, -40 순으로 출력할 것이고, 이 출력값의 부호를 다시 반대로 바꾸면 원래 데이터를 낮은 순서로 정렬한 것과 마찬가지가 됩니다.

PriorityQueue<int> queue = new PriorityQueue<int>();
// -30, 20, -10, 40을 부호를 반대로 입력
queue.Enqueue(30);
queue.Enqueue(-20);
queue.Enqueue(10);
queue.Enqueue(-40);

// 부호를 원래대로 돌리고 출력
while(queue.Count > 0)
    Console.WriteLine(queue.Dequeue() * -1);

사진 2. 낮은 값부터 가져오기