우선순위 큐? - 근데 이제 SortedDictionary 를 곁들인...

게임 이벤트를 개발하며 이런 생각을 했다.

여러개의 이벤트가 존재하는데
각 이벤트들의 시작여부를 판단하여 제어해야한다면?

별 생각 없이 작업을 했다면

public class GameEvent
{
    public long start_at;
    public ...
    public void Start()
    {
        //todo
    }
}

이런 이벤트 객체가 있다면 (Queue, List 등등..)

public class GameEventManager
{
    Queue<GameEvent> events = new Queue<GameEvent>();

    public void InitEvents()
    {
        foreach (var ev in events)
        {
            if (ev.start_at > DateTimeOffset.UtcNow.ToUnixTimeMilliseconds())
            {
                ev.Start();
            }
        }
    }
}

이런 형태로 단순히 돌았겠지만
모든 데이터를 다 돌아야한다는 점이 효율성이 좋아보이진 않았기에
이벤트가 시작되는 시간으로 정렬 후
시작 조건의 값이 False라면 그 이후로는 체크할 필요없는거 아닌가?
라는 생각에

우선순위 큐 라는것을 찾아보게되었다.
요점은 각 데이터들에게 우선순위를 정하고 데이터가 쌓인 순서가 아닌 우선순위를 기준으로 관리하는 방법

우선순위 큐에 대해서 구글링을 하면 많은 방법과 이진트리에 대해 설명이 있긴하지만
이미 정렬에 대한 기능이 있는 C#의 SortedDictionary를 이용해서 어렵지 않게 만들 수 있을 것 같다.
(그래도 우선순위 큐에서 정렬의 중요성에 대해 다른 글도 참고는 해보는게 좋겠다)

public class PriorityQueue<T>
{
    private SortedDictionary<int, Queue<T>> _priorityQueue = new SortedDictionary<int, Queue<T>>();

    public void Enqueue(T item, int priority)
    {
        if (!_priorityQueue.TryGetValue(priority, out var queue))
        {
            queue = new Queue<T>();
            _priorityQueue.Add(priority, queue);
        }
        queue.Enqueue(item);
    }

    public T Dequeue()
    {
        var highestPriority = _priorityQueue.Keys.First();
        var queue = _priorityQueue[highestPriority];
        var item = queue.Dequeue();
        if (queue.Count == 0)
        {
            _priorityQueue.Remove(highestPriority);
        }
        return item;
    }
    
    public T Peek()
    {
        var highestPriority = _priorityQueue.Keys.First();
        var queue = _priorityQueue[highestPriority];
        return queue.Peek();
    }

    public bool IsEmpty => _priorityQueue.Count == 0;
    
    public IEnumerator<T> GetEnumerator()
    {
        foreach (var queue in _priorityQueue.Values)
        {
            foreach (var item in queue)
            {
                yield return item;
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

EnQueue() : 데이터 추가 시 동일한 등급값이 있다면 해당 등급의 Queue에 추가
없다면 정렬된 키값의 새로운 Queue추가

DeQueue() : 우선순위 구조체 중 Keys.First() : 정렬되어있기에 Key의 First 값은 이미 우선순위가 높은 값이다
그 후 Queue의 Dequeue
해당 우선순위 Queue의 남은 데이터가 없다면 우선순위 키 삭제

예시 코드

    PriorityQueue<GameEvent> events = new PriorityQueue<GameEvent>();

    public void InitEvents()
    {
        events.Enqueue(new GameEvent(0), 0);
        events.Enqueue(new GameEvent(5), 5);
        events.Enqueue(new GameEvent(4), 4);
        events.Enqueue(new GameEvent(3), 3);
        events.Enqueue(new GameEvent(2), 2);
        events.Enqueue(new GameEvent(1), 1);

추가는 0,5,4,3,2,1 순으로 했지만 정렬은 0,1,2,3,4,5 오름차순으로 정렬된 모습

 

오름차순이 아니라 내림차순의 기능이 필요하다면
IComparer 인터페이스를 사용하여

public class DescendingComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return y.CompareTo(x);
    }
}

    private SortedDictionary<int, Queue<T>> _priorityQueue;

    public PriorityQueue(bool isAscending = true)
    {
        _priorityQueue = isAscedding 
            ? new SortedDictionary<int, Queue<T>>()
            : new SortedDictionary<int, Queue<T>>(new DescendingComparer<int>());
    }

위처럼 만들면 되지 않을까 싶다