우선순위 큐

전체 코드

using System.Collections.Generic;

namespace Exercise2
{
    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];
                _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--;

            // 역으로 내려가는 도장 깨기 시작
            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];
                _heap[now] = _heap[next];
                _heap[next] = temp;

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

        }
        public int Count()
        {
            return _heap.Count;
        }
    }
        internal 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()); 
            }
        }
    }
}

using System.Collections.Generic;

namespace Exercise2
{
    class PriorityQueue<T> where T : IComparable<T>
    {
        List<T> _heap = new List<T>();
        // O(logN)
        public void Push(T data)
        {
            // 힙의 맨 끝에 새로운 데이터를 삽입한다.
            _heap.Add(data);

            int now = _heap.Count - 1;
            // 도장 깨기

            while (now > 0)
            {
                // 도장 깨기 시도
                int next = (now - 1) / 2; // 부모의 인덱스
                if (_heap[now].CompareTo(_heap[next]) < 0)
                {
                    break; // 실패
                }
                // 두 값을 교체
                T temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

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

        }
        // O(logN)
        public T Pop()
        {
            // 반환할 데이터를 따로 저장
            T ret = _heap[0];

            // 마지막 데이터를 루트로 이동한다.
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);

            lastIndex--;

            // 역으로 내려가는 도장 깨기 시작
            int now = 0;
            while (true)
            {
                int left = 2 * now + 1;
                int right = 2 * now + 2;

                int next = now;
                // 왼쪽 값이 현재 값보다 크면 왼쪽으로 이동
                if (left <= lastIndex && _heap[next].CompareTo(_heap[left]) < 0)
                {
                    next = left;
                }
                // 오른값이 현재값보다 크면(왼쪽 이동 포함), 오른쪽으로 이동
                if (right <= lastIndex && _heap[next].CompareTo(_heap[left]) < 0)
                {
                    next = right;
                }
                // 왼쪽 / 오른쪽 모두 현재값보다 작으면 종료
                if (next == now)
                {
                    break;
                }

                // 두 값을 교채한다.
                T temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

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

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

    class Knight : IComparable<Knight>
    {
        public int Id { get; set; }

        public int CompareTo(Knight other)
        {
            if (Id == other.Id)
                return 0;
            return Id > other.Id ? 1 : -1;
            throw new NotImplementedException();
        }

        internal class Program
        {
            static void Main(string[] args)
            {
                PriorityQueue<Knight> q = new PriorityQueue<Knight>();
                q.Push(new Knight() { Id = 20});
                q.Push(new Knight() { Id = 10 });
                q.Push(new Knight() { Id = 30 });
                q.Push(new Knight() { Id = 90 });
                q.Push(new Knight() { Id = 40 });
                while (q.Count() > 0)
                {
                    Console.WriteLine(q.Pop().Id);
                }
                //// 작은 순으로 뽑고 싶은 경우
                //// 부호를 바꾼다
                //q.Push(-20);
                //q.Push(-10);
                //q.Push(-30);
                //q.Push(-90);
                //q.Push(-40);
                //while (q.Count() > 0)
                //{
                //    Console.WriteLine(-q.Pop()); 
                //}
            }
        }
    }
}

---

1. 우선순위 큐(Priority Queue)란?

우선순위 큐(Priority Queue)는 가장 우선순위가 높은 데이터가 먼저 처리되는 자료구조입니다.
일반적인 큐(Queue)는 FIFO(First In First Out) 구조로 동작하지만,
우선순위 큐는 우선순위가 높은 값이 먼저 나오는 방식으로 작동합니다.

2. 우선순위 큐의 활용 예시

• 운영체제의 작업 스케줄러 (CPU 스케줄링)
• 다익스트라 알고리즘 (Dijkstra)과 같은 그래프 탐색 알고리즘
• 이벤트 처리 시스템 (우선순위가 높은 이벤트를 먼저 처리)
• 멀티 태스킹 (시스템에서 중요한 작업을 먼저 실행)

---

3. 우선순위 큐 구현 방법

우선순위 큐는 여러 방법으로 구현할 수 있습니다.

구현 방법	삽입 시간	삭제 시간
리스트(List) 이용	O(1)	O(N)
힙(Heap) 이용	O(logN)	O(logN)

우선순위 큐를 배열(List)로 구현하면 삽입은 빠르지만, 가장 큰 값을 찾는 과정이 O(N)으로 느립니다.
그러나, 힙(Heap) 자료구조를 활용하면 삽입과 삭제 모두 O(logN) 이내에 수행할 수 있습니다.
따라서 우선순위 큐는 보통 힙을 기반으로 구현됩니다.

---

4. Max Heap을 활용한 우선순위 큐 구현

아래는 C#을 사용하여 최대 힙(Max Heap) 기반의 우선순위 큐를 구현한 코드입니다.
이 코드에서는 배열(List)을 사용하여 힙 트리를 관리하고 있습니다.

using System;
using System.Collections.Generic;

namespace Exercise2
{
    /// <summary>
    /// 최대 힙을 기반으로 한 우선순위 큐 클래스
    /// </summary>
    class PriorityQueue
    {
        // 힙을 저장할 리스트 (배열)
        private List<int> _heap = new List<int>();

        /// <summary>
        /// 데이터를 힙에 삽입 (Push 연산)
        /// </summary>
        public void Push(int data)
        {
            // 힙의 맨 끝에 새로운 데이터를 삽입한다.
            _heap.Add(data);

            // 삽입한 데이터의 현재 위치
            int now = _heap.Count - 1;

            // 힙의 구조를 유지하기 위해 부모와 비교하며 도장 깨기(Heapify-Up)
            while (now > 0)
            {
                int parent = (now - 1) / 2; // 부모 노드의 인덱스
                
                // 부모보다 작으면 종료 (최대 힙 유지)
                if (_heap[now] <= _heap[parent])
                    break;

                // 부모와 자식 위치 교체
                Swap(now, parent);

                // 검사 위치 이동 (위로 올라감)
                now = parent;
            }
        }

        /// <summary>
        /// 최대값을 힙에서 제거하고 반환 (Pop 연산)
        /// </summary>
        public int Pop()
        {
            if (_heap.Count == 0)
                throw new InvalidOperationException("큐가 비어 있습니다.");

            // 최댓값(루트 노드)을 저장
            int ret = _heap[0];

            // 마지막 노드를 루트로 이동
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);
            lastIndex--;

            // 힙 속성을 유지하기 위해 도장 깨기(Heapify-Down)
            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;

                // 현재 노드와 변경할 노드 위치 교체
                Swap(now, next);

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

        /// <summary>
        /// 현재 큐에 저장된 요소 개수를 반환
        /// </summary>
        public int Count()
        {
            return _heap.Count;
        }

        /// <summary>
        /// 리스트 내부의 두 원소를 교체하는 메서드
        /// </summary>
        private void Swap(int a, int b)
        {
            int temp = _heap[a];
            _heap[a] = _heap[b];
            _heap[b] = temp;
        }
    }

    /// <summary>
    /// 실행을 위한 메인 프로그램
    /// </summary>
    internal class Program
    {
        static void Main(string[] args)
        {
            // 우선순위 큐 생성
            PriorityQueue pq = new PriorityQueue();
            
            // 데이터 삽입
            pq.Push(20);
            pq.Push(10);
            pq.Push(30);
            pq.Push(90);
            pq.Push(40);

            // 데이터를 하나씩 꺼내면서 출력
            while (pq.Count() > 0)
            {
                Console.WriteLine(pq.Pop()); // 90 40 30 20 10 출력
            }
        }
    }
}

---

5. 코드 설명

(1) Push 연산 (Heapify-Up)

• 새로운 데이터를 리스트의 맨 끝에 추가
• 부모 노드와 비교하면서 값이 더 크면 위치를 교환
• O(logN) 시간 복잡도

(2) Pop 연산 (Heapify-Down)

• 루트(최댓값) 제거 후, 마지막 데이터를 루트로 이동
• 자식 노드와 비교하면서 더 큰 값과 교환 (힙 속성 유지)
• O(logN) 시간 복잡도

(3) Count 연산

• 현재 힙에 저장된 노드 개수 반환
• O(1) 시간 복잡도

(4) Swap 메서드

• 리스트의 두 원소를 교환하는 유틸리티 함수

---

6. 실행 결과

90
40
30
20
10

입력한 데이터 중 가장 큰 값이 먼저 출력되는 것을 확인할 수 있습니다.

---

1. IComparable 인터페이스를 활용한 비교

우선순위 큐는 최대 힙(Max Heap) 또는 최소 힙(Min Heap) 구조를 유지하면서 항상 부모 노드가 자식 노드보다 크거나(최대 힙) 작도록(최소 힙) 정렬하는 자료구조입니다.
하지만 int 같은 기본 자료형이 아닌 사용자 정의 객체 타입을 넣으려면, 비교 기준이 필요합니다.
이를 위해 IComparable 인터페이스를 상속받아 비교 메서드(CompareTo)를 구현해야 합니다.

---

2. 우선순위 큐의 비교 방법

IComparable<T> 인터페이스를 활용하여 CompareTo 메서드를 구현하면 객체를 정렬할 기준을 직접 설정할 수 있습니다.

• CompareTo 구현 방식
  • a.CompareTo(b)
    • a > b이면 1 반환 (a가 더 크다)
    • a < b이면 -1 반환 (b가 더 크다)
    • a == b이면 0 반환 (동일)

---

3. 제네릭(Generic) 기반 우선순위 큐 구현

using System;
using System.Collections.Generic;

namespace Exercise2
{
    /// <summary>
    /// 제네릭 기반 최대 힙 우선순위 큐
    /// </summary>
    class PriorityQueue<T> where T : IComparable<T>
    {
        private List<T> _heap = new List<T>();

        /// <summary>
        /// 데이터를 힙에 삽입 (Push 연산)
        /// </summary>
        public void Push(T data)
        {
            // 힙의 맨 끝에 새로운 데이터를 삽입
            _heap.Add(data);

            int now = _heap.Count - 1;

            // Heapify-Up (부모와 비교하여 자리 찾기)
            while (now > 0)
            {
                int parent = (now - 1) / 2; // 부모 인덱스

                // 부모보다 작으면 종료 (최대 힙 유지)
                if (_heap[now].CompareTo(_heap[parent]) <= 0)
                    break;

                // 부모와 자식 위치 교환
                Swap(now, parent);

                // 검사 위치 이동
                now = parent;
            }
        }

        /// <summary>
        /// 최대값을 힙에서 제거하고 반환 (Pop 연산)
        /// </summary>
        public T Pop()
        {
            if (_heap.Count == 0)
                throw new InvalidOperationException("큐가 비어 있습니다.");

            // 최댓값(루트 노드) 저장
            T ret = _heap[0];

            // 마지막 데이터를 루트로 이동
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);
            lastIndex--;

            // Heapify-Down (자식과 비교하여 자리 찾기)
            int now = 0;
            while (true)
            {
                int left = 2 * now + 1;  // 왼쪽 자식 노드
                int right = 2 * now + 2; // 오른쪽 자식 노드
                int next = now;

                // 왼쪽 자식이 더 크면 이동 대상 업데이트
                if (left <= lastIndex && _heap[next].CompareTo(_heap[left]) < 0)
                    next = left;

                // 오른쪽 자식이 더 크면 이동 대상 업데이트
                if (right <= lastIndex && _heap[next].CompareTo(_heap[right]) < 0)
                    next = right;

                // 이동할 필요 없으면 종료
                if (next == now)
                    break;

                // 현재 노드와 변경할 노드 위치 교환
                Swap(now, next);

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

            return ret;
        }

        /// <summary>
        /// 현재 큐에 저장된 요소 개수를 반환
        /// </summary>
        public int Count()
        {
            return _heap.Count;
        }

        /// <summary>
        /// 리스트 내부의 두 원소를 교체하는 메서드
        /// </summary>
        private void Swap(int a, int b)
        {
            T temp = _heap[a];
            _heap[a] = _heap[b];
            _heap[b] = temp;
        }
    }

    /// <summary>
    /// 비교 가능한 객체: Knight 클래스
    /// </summary>
    class Knight : IComparable<Knight>
    {
        public int Id { get; set; }

        /// <summary>
        /// 비교 연산을 위한 CompareTo 메서드
        /// </summary>
        public int CompareTo(Knight other)
        {
            if (Id == other.Id)
                return 0;
            return Id > other.Id ? 1 : -1;
        }
    }

    internal class Program
    {
        static void Main(string[] args)
        {
            // 우선순위 큐 생성 (Knight 객체를 저장하는 최대 힙)
            PriorityQueue<Knight> q = new PriorityQueue<Knight>();

            // 데이터 삽입
            q.Push(new Knight() { Id = 20 });
            q.Push(new Knight() { Id = 10 });
            q.Push(new Knight() { Id = 30 });
            q.Push(new Knight() { Id = 90 });
            q.Push(new Knight() { Id = 40 });

            // 데이터를 하나씩 꺼내면서 출력 (Id 기준으로 큰 순서대로 출력)
            while (q.Count() > 0)
            {
                Console.WriteLine(q.Pop().Id);
            }

            // 최소 힙으로 사용하고 싶은 경우 (부호 변경)
            /*
            q.Push(new Knight() { Id = -20 });
            q.Push(new Knight() { Id = -10 });
            q.Push(new Knight() { Id = -30 });
            q.Push(new Knight() { Id = -90 });
            q.Push(new Knight() { Id = -40 });

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

---

4. 코드 설명

(1) PriorityQueue 클래스

• 제네릭을 활용하여 모든 비교 가능한 타입(T)을 저장 가능하도록 설계
• IComparable<T>을 요구(where T : IComparable<T>)하여 비교 연산이 가능한 타입만 저장 가능
• 힙 트리 유지 (Push: Heapify-Up, Pop: Heapify-Down)
• O(logN) 시간 복잡도

(2) Knight 클래스

• IComparable 인터페이스 구현
• CompareTo(Knight other) 메서드에서 Id를 기준으로 비교
• 우선순위 큐가 Id가 큰 Knight부터 꺼낼 수 있도록 설정

---

5. 실행 결과

90
40
30
20
10

Knight 객체의 Id 값이 큰 순서대로 출력되는 것을 확인할 수 있습니다.

---

6. 최소 힙(Min Heap)으로 사용하고 싶다면?

최대 힙이 아니라 작은 값부터 뽑고 싶은 경우, CompareTo 비교 방식 변경하거나 부호를 바꾸어 삽입하면 됩니다.

(1) CompareTo 변경

public int CompareTo(Knight other)
{
    return Id.CompareTo(other.Id) * -1; // 부호 반전
}

(2) 부호 변경 후 사용

q.Push(new Knight() { Id = -20 });
q.Push(new Knight() { Id = -10 });
q.Push(new Knight() { Id = -30 });
q.Push(new Knight() { Id = -90 });
q.Push(new Knight() { Id = -40 });

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

이렇게 하면 작은 값부터 출력되는 최소 힙을 만들 수 있습니다.

---