우선순위 큐 구현 연습

📌 우선순위 큐란?

• 일반적인 큐(선입선출 FIFO)와 달리, 데이터의 우선순위에 따라 먼저 나오는 큐.
• 힙(Heap) 트리 자료구조로 구현되어, top()은 항상 최우선값을 보장함.
• C++ STL의 priority_queue가 대표적인 예시.

---

📦 클래스 템플릿 기본 구조

template<typename T, typename Container = vector<T>, typename Predicate = less<T>>
class PriorityQueue

• T: 데이터 타입
• Container: 내부 저장소, 기본 vector<T>
• Predicate: 비교 기준 (기본 less<T> → Max Heap)

greater<T>를 넘기면 Min Heap을 만들 수 있어요!

---

📥 push(): 힙 정렬 (상향식 Heapify)

void push(const T& data)
{
    _heap.push_back(data); // 마지막에 삽입
    int now = _heap.size() - 1;

    while (now > 0)
    {
        int parent = (now - 1) / 2;
        if (_predicate(_heap[now], _heap[parent]))
            break;

        swap(_heap[now], _heap[parent]);
        now = parent;
    }
}

📘 정리

• 완전 이진 트리 규칙을 유지하며 가장 끝에 삽입
• parent = (i-1)/2로 부모와 비교
• 우선순위 규칙을 깨면 위로 올라가며 교체 (도장깨기!)

---

🧹 pop(): 힙 정렬 (하향식 Heapify)

void pop()
{
    _heap[0] = _heap.back(); // 루트에 마지막 값 복사
    _heap.pop_back();

    int now = 0;
    while (true)
    {
        int left = 2 * now + 1;
        int right = 2 * now + 2;
        if (left >= _heap.size())
            break;

        int next = now;
        if (_predicate(_heap[next], _heap[left])) next = left;
        if (right < _heap.size() && _predicate(_heap[next], _heap[right])) next = right;

        if (next == now) break;

        swap(_heap[now], _heap[next]);
        now = next;
    }
}

📘 정리

• 루트 제거 후 마지막 노드로 대체
• 아래로 내려가며 우선순위 위반 시 자식과 교체
• left = 2*i+1, right = 2*i+2 → 배열 기반 완전 이진 트리 규칙

---

🧠 top() & empty()

T& top()        { return _heap[0]; }
bool empty()    { return _heap.empty(); }

• top(): 현재 힙의 최우선 값 반환 (Max or Min 기준)
• empty(): 데이터 유무 확인

---

⚙️ 전체 코드 예제

int main()
{
    PriorityQueue<int, vector<int>, greater<int>> pq; // Min Heap

    pq.push(100); pq.push(300); pq.push(200);
    pq.push(500); pq.push(400);

    while (!pq.empty())
    {
        cout << pq.top() << endl;
        pq.pop();
    }
}

출력 결과:

100
200
300
400
500

---

🧩 힙의 구현 핵심 요약

개념	인덱스 공식
부모	(i - 1) / 2
왼쪽 자식	2 * i + 1
오른쪽 자식	2 * i + 2

• 완전 이진 트리 기반 배열 구조 사용
• 삽입/삭제 시 O(log N) 시간 복잡도 보장

---

🌟 정렬 기준 바꾸기: Predicate

조건	설정 방법
Max Heap	less<T> (기본값)
Min Heap	greater<T>
커스텀 우선순위	struct MyCompare { bool operator()(...) }

---