[C#] 우선순위 큐

우선순위 큐

 - 큐는 먼저 들어온 데이터가 먼저 나가는 구조 즉, FIFO구조였습니다. 그런데 우선순위 큐는 들어간 순서가 아닌 우선순위가 높은 순서로대로 데이터가 먼저 나오게 됩니다. 우선순위 큐는 힙을 이용하여 구현할 수 있습니다.

 1) 새로운 값 추가 Push()

 2) 최대값 꺼내기 Pop()

 

using System;
using System.Collections.Generic;
using System.Text;

namespace Exercise
{ 
    class PriorityQueue
    {
        List<int> _heap = new List<int>();

        public void Push(int data) //새로운 값 추가
        {
            //새로운 값 추가(힙의 맨 끝에 새로운 데이터 삽입)
            _heap.Add(data);

            int now = _heap.Count - 1;
            //새로운 값과 부모노드를 비교해서 부모노드가 새로운값보다 작으면 부모노드와 새로운값은 위치를 교체 한다.
            while (now > 0)
            {
                int next = (now - 1) / 2;
                if (_heap[now] < _heap[next]) //새로운값이 부모노드보다 작으면 교체를 멈춘다.
                    break;

                //새로운 값이 부모노드보다 크면 교체해준다.
                int temp = _heap[now]; //임시 temp에 새로운 값을 임시 저장
                _heap[now] = _heap[next]; //부모노드와 자식노드를 교체해준다.
                _heap[next] = temp; //임시저장된 새로운 값은 부모노드가 된다.

                //검사 위치를 이동
                now = next;
            }
        }

        public int Pop() //최대값 꺼내기
        {
            // 반환할 데이터를 따로 저장
            int ret = _heap[0];

            //마지막 데이터를 루트로 이동
            int lastIndex = _heap.Count - 1; //마지막 번호
            _heap[0] = _heap[lastIndex]; //마지막 데이터가 최상위 데이터가 된다.
            _heap.RemoveAt(lastIndex); //이동을 마친 마지막 데이터는 삭제
            lastIndex--; //데이터 1개가 줄었으니깐 줄인다.

            //역으로 부모 노드와 제일 큰 자식노드를 비교하여 부모 노드값이 자식노드 값보다 작으면 자리를 바꿔준다.
            int now = 0;
            while (true)
            {
                int left = 2 * now + 1; //왼쪽 좌표
                int right = 2 * now + 2; //오른쪽 좌표

                int next = now;
                //왼쪽 값이 현재 값보다 크면 , 왼쪽으로 이동
                if (left <= lastIndex && _heap[next] < _heap[left])
                    next = left;
                //오른쪽 값이 현재 값(왼쪽 이동 포함)보다 크면, 오른쪽으로 이동
                if (right <= lastIndex && _heap[next] < _heap[right])
                    next = right;

                //왼쪽, 오른쪽 모두 현재 값보다 작으면 종료
                if (next == now)
                    break;

                //두 값을 교체한다(부모노드가 자식노드보다 작으면 교체)
                int temp = _heap[now]; //임시 temp에 새로운 값을 임시 저장
                _heap[now] = _heap[next]; //부모노드와 자식노드를 교체해준다.
                _heap[next] = temp; //임시저장된 새로운 값은 부모노드가 된다.

                now = next;
            }


            return ret;
        }
        
        public int Count()
        {
            return _heap.Count;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            PriorityQueue q = new PriorityQueue();
            q.Push(20);
            q.Push(10);
            q.Push(30);
            q.Push(90);
            q.Push(40);

            while (q.Count() > 0)
            {
                Console.WriteLine(q.Pop());
            }
        }
    }
}

 

출력

우선순위 큐 출력

 

만약 예제처럼 큰 수 순서로 나오는게 아닌 작은 순서대로 출력하는 방법은 밑에 예제처럼 -부호를 붙여주면 됩니다.

    class Program
    {
        static void Main(string[] args)
        {
            PriorityQueue q = new PriorityQueue();
            q.Push(-20);
            q.Push(-10);
            q.Push(-30);
            q.Push(-90);
            q.Push(-40);

            while (q.Count() > 0)
            {
                Console.WriteLine(-q.Pop());
            }
        }
    }

 

출력

-를 붙인 우선순위 큐

 

 

 

 

---------------------------------------------------------------------------------------------------------------------------

참고 : [인프런] Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘