우선순위 큐 (최대 힙, 최대 힙)

🧮우선순위 큐 (Priority Queue)

우선순위 큐(Priority Queue) 는 일반 큐(Queue)와 달리
데이터를 꺼낼 때 가장 먼저 들어온 순서(FIFO) 가 아니라,
우선순위가 높은 데이터가 먼저 나오는 구조입니다.

🔹 기본 개념

구분	일반 큐(Queue)	우선순위 큐(Priority Queue)
데이터 추가	뒤에 삽입	트리 구조의 말단에 삽입
데이터 제거	앞에서 제거	가장 높은 우선순위 제거
정렬 기준	삽입 순서	값(또는 비교함수)에 따라 자동 정렬
내부 구조	선형 자료구조	힙(Heap) 구조 기반 (완전이진트리)

✅ C++ STL의 priority_queue 는 내부적으로 Max Heap 을 기본으로 사용합니다.

🧩 동작 원리

1️⃣ Node Push (삽입 과정)

1. 가장 말단 위치에 새 노드를 삽입
2. 부모 노드와 값을 비교
3. 부모보다 우선순위가 높다면 교체(Heapify-Up)
4. 루트(root)까지 반복 수행

Push 예시 (Max Heap 기준)
[10, 7, 5] 상태에서 12 삽입 → [10, 7, 5, 12]
→ 부모(10)보다 크므로 교체 → [12, 10, 5, 7]

2️⃣ Node Pop (삭제 과정)

1. 루트 노드(최우선 노드) 를 제거
2. 말단 노드를 루트 자리로 이동
3. 자식 노드들과 비교
4. 자식 중 더 큰 노드와 교체(Heapify-Down)
5. 말단까지 반복
   Pop 예시 (Max Heap 기준)

[12, 10, 5, 7] → 루트(12) 제거
→ 마지막 노드(7)를 루트로 이동 → [7, 10, 5]
→ 자식(10)보다 작으므로 교체 → [10, 7, 5]

⚙️ C++ 예시 코드

🔹 1️⃣ 최대 힙 (Max Heap)

가장 큰 값이 우선순위가 높다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    priority_queue<int> MaxQue;  // 기본: Max Heap
    int n;

    while (1) {
        cin >> n;

        if (n == 0) {
            if (MaxQue.empty()) cout << "-1\n";  // 비었을 때 예외 처리
            else {
                cout << MaxQue.top() << "\n";    // 가장 큰 값 출력
                MaxQue.pop();                    // 제거
            }
        }
        else if (n == -1) break; // 종료
        else MaxQue.push(n);     // 삽입
    }

    return 0;
}

2️⃣ 최소 힙 (Min Heap)

가장 작은 값이 우선순위가 높다.

✅ 부호 반전 trick (-값으로 저장)

priority_queue<int> MinQue; // 여전히 Max Heap 구조

MinQue.push(-n); // push 시 부호 반전
cout << -MinQue.top(); // pop 시 다시 -붙여 복원
MinQue.pop();

📘 정리 문장

C++의 priority_queue는 기본적으로 최대 힙(Max Heap) 구조를 사용하며,
최소 힙(Min Heap) 을 만들려면 greater<> 비교자나 부호 반전 trick 을 사용한다.