[C#] priority Queue 구현

priority Queue

---

이번 주말에 A* 알고리즘을 구현하고자 했는데, A* 알고리즘의 구현의 경우 우선순위 큐의 구현이 선행되어야해서 우선순위 큐의 구현부터 먼저 해보기로 했다. 우선순위 큐는 저장된 데이터 중 가장 우선순위가 높은 데이터를 우선적으로 출력하는 자료구조로 자세한 정리는 priority Queue를 참고하면 된다.

property

구현은 모든 데이터에 대응이 가능하도록 제네릭으로 진행하였고, 우선순위를 비교해야하므로 T는 IComparable을 상속받은 타입으로 제한하였다. 다음은 힙 트리 구조의 배열로 구현한 우선순위 큐의 속성이다.

class PriorityQueue<T> where T : IComparable<T>
{
    #region property

    private T[] _data;
    public int Count { get; private set; }
    public int Capacity { get; private set; }

    #endregion
}

데이터 구조인 배열 및 배열의 최대 크기인 Capacity와 배열의 개수인 Count를 가진다.

생성자

기본 생성자와 함께 외부에서 capacity가 주어지는 경우 해당 값으로 capacity를 갖는 생성자를 오버로딩으로 추가했다.

class PriorityQueue<T> where T : IComparable<T>
{
	#region 생성자

    public PriorityQueue()
    {
        Count = 0;
        Capacity = 1;
        _data = new T[Capacity];
    }

    public PriorityQueue(int capacity)
    {
        Count = 0;
        Capacity = capacity;
        _data = new T[Capacity];
    }

    #endregion
}

private Method

클래스 내부에서 주로 사용하는 기능을 private method로 만들어 사용했다. Expand()의 경우 Capacity와 Count를 비교하여 Count가 Capacity 이상인 경우 배열의 크기를 확장하는 기능이며, Swap()은 단순히 두 값을 바꾸는 기능이다.

class PriorityQueue<T> where T : IComparable<T>
{
	#region private func

    private void Expand()
    {
        T[] newData = new T[Capacity * 2];
        
        for (int i = 0; i < Count; i++)
        {
            newData[i] = _data[i];
        }

        _data = newData;
        Capacity *= 2;
    }

    private void Swap(ref T left, ref T right)
    {
        T temp = left;
        left = right;
        right = temp;
    }

    #endregion
}

public Method

이전에 우선순위 큐를 다루면서 언급한 3가지 기능(Enqueue, Dequeue, Peek)을 구현했다. 다만 힙 트리 구조를 유지하기 위한 반복 스왑 구간이 Enqueue와 Dequeue에 존재한다.

class PriorityQueue<T> where T : IComparable<T>
{
	#region public func

    public void Enqueue(T value)
    {
        // 배열이 꽉 찼을 경우 확장
        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;
            }

            Swap(ref _data[now], ref _data[parent]);
            now = parent;
        }
    }

    public T Dequeue()
    {
        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;
            
            if (left < Count && _data[next].CompareTo(_data[left]) < 0)
            {
                next = left;
            }

            if (right < Count && _data[next].CompareTo(_data[right]) < 0)
            {
                next = right;
            }

            if (next == now)
            {
                break;
            }
            
            Swap(ref _data[now], ref _data[next]);
            now = next;
        }
        return result;
    }

    public T Peek()
    {
        if (Count == 0)
        {
            throw new IndexOutOfRangeException();
        }

        return _data[0];
    }

    #endregion
}

자식 노드와 비교하는 조건인 if (left < Count && _data[next].CompareTo(_data[left]) < 0)에서 left < Count가 없을 경우 left가 Count를 넘어가게 되어 null 참조 오류가 발생할 위험이 있다.

test code

---

구현한 우선순위 큐를 테스트하기 위해 작성한 코드와 결과는 다음과 같다.

class Monster : IComparable<Monster>
{
    public int Level;
    public Monster(int lv)
    {
        Level = lv;
    }
    
    public int CompareTo(Monster other)
    {
        if (Level == other.Level)
        {
            return 0;
        }

        return Level > other.Level ? 1 : -1;
    }
}

class Program
{
    static void Main(string[] args)
    {
        PriorityQueue<Monster> queue = new PriorityQueue<Monster>();
        
        queue.Enqueue(new Monster(6));
        queue.Enqueue(new Monster(2));
        queue.Enqueue(new Monster(9));
        queue.Enqueue(new Monster(1));
        queue.Enqueue(new Monster(3));

        while (queue.Count > 0)
        {
            Console.WriteLine(queue.Dequeue().Level);
        }
    }
}

9
6
3
2
1