🚀 우선 순위 큐

• 우선 순위 큐는 우선 순위가 높을 수록 먼저 출력하는 자료구조이다.
• 우선순위 큐 구현에 쓰이는 대표적인 자료구조로는 heap(힙)이 있다.

🚀 힙 트리 특징

• 완전 이진 트리의 일종
• 부모 노드가 가진 값은 자식 노드가 가진 값보다 크다
• 마지막 레벨을 제외한 모든 레벨에 노드가 있다
• 마지막 레벨의 노드는 항상 왼쪽부터 채워넣어야 한다
• 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다

배열만 이용하여도 힙 구조를 표현 가능하다
i번 노드의 왼쪽 자식은 2 i + 1
i번 노드의 오른쪽 자식은 2 i + 2
i번 노드의 부모는 (i - 1) / 2 (나머지는 버린다)

값 추가

• 완전 이진 트리이며, 왼쪽 부터 값을 채워넣기에 위치를 확정 가능
• 부모 노드가 가진 값은 항상 자식 보다 커야하므로 채워넣은 값이 더 크다면 위치를 계속해서 바꿔준다

최대값 꺼내기

• 최대값은 무조건 루트이므로 루트를 제외한다.
• 마지막으로 추가된 값을 루트로 올리고 자식 노드의 값이 더 크다면 위치 재조정을 한다.

힙 트리로 우선 순위 큐 구현

//Monster 클래스
    class Monster : IComparable<Monster> //우선 순위를 비교하기 위해 인터페이스 상속
    {
        // 우선 순위를 비교할 정수형 변수 Id 
        public int Id;

        public Monster(int id)
        {
            Id = id;
        }

        public int CompareTo(Monster other)
        {
            if (Id == other.Id)
                return 0;

            return Id < other.Id ? 1 : -1;

            throw new NotImplementedException();
        }
    }

    class PriorityQueue<T> where T : IComparable<T>
    {
        //힙을 표현할 리스트 생성
        private List<T> _heap = new List<T>();
        public int Count
        {
            get { return _heap.Count; }
        }
        
        //값을 넣어줄 Push함수
        public void Push(T data)
        {
            _heap.Add(data);
            int now = Count - 1;

            //부모 노드와의 값을 비교해 위치를 조정해준다.
            while (now > 0)
            {
                int next = (now - 1) / 2;

                if (_heap[now].CompareTo(_heap[next]) < 0)
                    break;

                T temp = _heap[next];
                _heap[next] = _heap[now];
                _heap[now] = temp;

                now = next;
            }
        }

        // root를 꺼내줄 Pop 함수
        public T Pop()
        {
            T ret = _heap[0]; // 반환할 값 저장
            int lastIndex = Count - 1;

            //마지막에 추가한 값을 root로 옮겨준다
            _heap[0] = _heap[lastIndex];  
            _heap.RemoveAt(lastIndex);  
            lastIndex--;

            int now = 0;

            //자식 노드와의 값을 비교해 위치를 조정해준다.
            while (true)
            {
                int left = now * 2 + 1;
                int right = now * 2 + 2;

                int next = now;

                if (lastIndex >= left && _heap[next].CompareTo(_heap[left]) < 0)
                    next = left;
                if (lastIndex >= right && _heap[next].CompareTo(_heap[right]) < 0)
                    next = right;

                if (next == now)
                    break;

                T temp = _heap[next];
                _heap[next] = _heap[now];
                _heap[now] = temp;

                now = next;
            }

            return ret;
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            PriorityQueue<Monster> priorityQueue = new PriorityQueue<Monster>();

            priorityQueue.Push(new Monster(30));
            priorityQueue.Push(new Monster(70));
            priorityQueue.Push(new Monster(40));
            priorityQueue.Push(new Monster(60));
            priorityQueue.Push(new Monster(90));

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

            Console.ReadKey();
        }
        

정상적으로 우선순위에 따라 출력된 것을 볼 수 있다.