C#, 우선순위 큐 개념과 힙을 통한 구현

우선순위 큐란?

큐(Qeueu)는 FIFO(First In First Out) 방식을 따르기 때문에, 입력 순서대로 출력되는 데이터 구조인 반면, 우선순위 큐(Priority Qeueu)는 입력 순서와는 무관하게 우선순위대로 출력되는 데이터 구조입니다.

시간 복잡도

https://www.bigocheatsheet.com/

우선 순위 큐는 Enqueue()시, 내부적으로 정렬을 해주거나 또는 탐색을 해주어야하는 로직이 필요합니다. 우선 순위대로 정렬하거나 탐색하는 방법으로 얼마나 효율적으로 만드느냐가 주제의 핵심 포인트가 되겠습니다. 이 글에서는 'O(N)'과 'O(logN)' 두 가지 방식을 다룹니다.

우선순위 큐 구현 방법과 종류

이진 탐색'O(logN)'과 단순 선형 탐색 차이'O(N)'

• Queue의 Enqueue()시, 내부적으로 효율적인 탐색 방법이 필요하다.
• 간단한 구현 방식으로는 'O(N)'의 복잡도를 가지고 있는 단순 선형 탐색이 있으며,
• 대표적으로 알려진 'O(logN)'의 복잡도를 가지고 있는 이진 탐색 방식이 있다.

스크립트, 단순 선형 탐색 'O(N)'

처음부터 끝까지 우선 순위를 탐색하는 방식으로 길이가 짧을 때 유용하겠습니다. 단순 연결 리스트 구조로 구현되어 있어, 이해하기 쉬우며, 복잡하지 않고 무겁지 않은 구조를 가지고 있습니다. 다만 대량의 큐를 넣어야한다면 추천하지 않습니다.

public class PriorityQueue<T>
{
    private class Node
    {
        public T Data { get; private set; }
        public int Priority { get; set; } = 0;

        public Node prve;
        public Node next;

        public Node(T data, int priority)
        {
            this.Data = data;
            this.Priority = priority;
        }
    }

    private Node head = null;
    private Node tail = null;

    public int Count = 0;

    public void Enqueue(T data, int priority)
    {
        ++Count;
        Node newNode = new Node(data, priority);
        if (head != null)
        {
            Node prev = null;
            Node node = head;

            //////////////////////////////
            /// 처음부터 탐색한다. 'O(N)'
            do
            {
                if (node.Priority > priority) break;
                prev = node;
                node = node.next;
            } while (node != null);
            //////////////////////////////

            if (prev != null)
                prev.next = newNode;

            newNode.prve = prev;

            if (node != null)
            {
                if (node.Priority > priority)
                {
                    newNode.next = node;
                    node.prve = newNode;
                }
                else
                {
                    node.next = newNode;
                    newNode.prve = node;
                }
            }

            if (newNode.prve == null)
                head = newNode;

            if (newNode.next == null)
                tail = newNode;
        }
        else
        {
            head = newNode;
            tail = head;
        }
    }

    public T Dequeue()
    {
        --Count;
        Node temp = tail;
        tail = tail.prve;
        if (tail == null) head = null;

        if (tail != null && tail.prve != null)
            tail.prve.next = null;

        if (temp != null)
            return temp.Data;
        return default(T);
    }

    public T Peek()
    {
        if (tail != null)
            return tail.Data;
        return default(T);
    }
}

스크립트, 이진 탐색 방식 'O(logN)'

대량의 큐를 집어 넣어야하는 경우, 이진 탐색 방식을 이용하여 적절한 타겟을 찾습니다. 이론상, O(N) 방식보다 효율적이며 범용적으로 쓰이는 방식이 되겠습니다. 다만 조금 아쉬운 부분으로는, List의 Insert()가 들어가기 때문에 비용이 좀 더 나올 수 있겠습니다.

using System.Collections.Generic;

public class PriorityQueue<T>
{
    private class Node
    {
        public T Data { get; private set; }
        public int Priority { get; set; } = 0;

        public Node(T data, int priority)
        {
            this.Data = data;
            this.Priority = priority;
        }
    }

    private List<Node> nodes = new List<Node>();

    public int Count => nodes.Count;

    public void Enqueue(T data, int priority)
    {
        Node newNode = new Node(data, priority);
        if (nodes.Count == 0)
        {
            nodes.Add(newNode);
        }
        else
        {
            //////////////////////////////
            // 이진 탐색을 시작한다. 'O(logN)'
            int start = 0;
            int end = nodes.Count - 1;
            int harf = 0;
            while (start != end)
            {
                if (end - start == 1)
                {
                    if (nodes[start].Priority < priority)
                    {
                        harf = end;
                    }
                    else
                    {
                        harf = start;
                    }
                    break;
                }
                else
                {
                    harf = start + ((end - start) / 2);
                    if (nodes[harf].Priority > priority)
                    {
                        // Down
                        end = harf;
                    }
                    else
                    {
                        // Up
                        start = harf;
                    }
                }
            }
            //////////////////////////////

            if (nodes[harf].Priority > priority)
                nodes.Insert(harf, newNode);
            else
                nodes.Insert(harf + 1, newNode);
        }
    }

    public T Dequeue()
    {
        Node tail = null;
        
        if (Count > 0)
        {
            tail = nodes[nodes.Count - 1];
            nodes.RemoveAt(nodes.Count - 1);
        }

        if (tail != null)
            return tail.Data;
        return default(T);
    }

    public T Peek()
    {
        Node tail = null;
        
        if (Count > 0)
            tail = nodes[nodes.Count - 1];

        if (tail != null)
            return tail.Data;
        return default(T);
    }
}

예제

위의 두가지의 스크립트는 아래와 같은 결과를 도출해냅니다.

우선 순위 값이 클 수록 우선 순위가 높습니다.

PriorityQueue<int> priorityQueue = new PriorityQueue<int>();
priorityQueue.Enqueue(9, 1);
priorityQueue.Enqueue(8, 2);
priorityQueue.Enqueue(7, 3);
priorityQueue.Enqueue(6, 0);
while (priorityQueue.Count > 0)
{
    Console.WriteLine(priorityQueue.Dequeue());
}

결과

참고 자료 및 이미지 출처 : https://docs.microsoft.com/ko-kr/azure/architecture/patterns/priority-queue