참고 자료
http://www.cplusplus.com/reference/queue/priority_queue/
https://blockdmask.tistory.com/107
https://kbj96.tistory.com/15
https://hydroponicglass.tistory.com/169

priority_queue는 C++의 STL 컨테이너 중 하나로서, 내부적으로 힙 자료구조로 구현된 우선순위 큐를 편하게 사용할 수 있게 해준다. <queue> 헤더파일에 포함되어 있다.

template <class T,
class Container = vector,
class Compare = less<typename Container::value_type>>
class priority_queue;

• 우선순위 큐는 기본적으로 vector 컨테이너로 구현되어 있지만, dequeue와 함께 사용할 수도 있다.
• 정렬 기준은 기본적으로 내림차순(less<T>)이지만, 이 역시도 기준을 바꿀 수 있다.
• 기본 생성자 형식: priority_queue pq;
• 내부 컨테이너 변경: priority_queue<int, deque<int>> pq;
• 정렬 기준 변경: priority_queue<int , vector, greater<int>> pq;

기본 사용법

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

int main() {
    // priority_queue<int, vector<int>, less<int>> pq;
    priority_queue<int> pq; // 내림차순

    // 원소 삽입 (가장 큰 값이 top에 오도록)
    pq.push(4);
    pq.push(7);
    pq.push(3);
    pq.push(1);
    pq.push(10);

    cout << pq.size() << "\n"; // 5

    while (!pq.empty()) {
        cout << pq.top() << " "; // 10 7 4 3 1
        pq.pop();
    }

    return 0;
}

가장 작은 값부터 오름차순으로 출력하려면, priority_queue<int , vector<int>, greater<int>> pq; 이렇게 선언해주거나, 원소를 push할 때부터 음수로 변환해서 넣는 방법도 있다. 그러면 우선순위 큐는 기본적으로 가장 큰 값이 top에 오도록 하기 때문에, 음수 중에서 절댓값이 가장 작은 원소부터 오름차순으로 출력된다.

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

int main() {
  // 오름차순
  priority_queue<int, vector<int>, greater<int>> pq;

  // 원소 삽입 (가장 작은 값이 top에 오도록)
  pq.push(4);
  pq.push(7);
  pq.push(3);
  pq.push(1);
  pq.push(10);

  cout << pq.size() << "\n"; // 5

  while (!pq.empty()) {
      cout << pq.top() << " "; // 1 3 4 7 10
      pq.pop();
  }

  return 0;
}

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

int main() {
  priority_queue<int> pq;

  // 음수로 변환해서 원소 삽입
  pq.push(-4);
  pq.push(-7);
  pq.push(-3);
  pq.push(-1);
  pq.push(-10);

  cout << pq.size() << "\n"; // 5

  // 절댓값이 작은 원소부터 출력되도록 (오름차순)
  while (!pq.empty()) {
      cout << -pq.top() << " "; // 1 3 4 7 10
      pq.pop();
  }

  return 0;
}

백준 11286번. 절댓값 힙

https://www.acmicpc.net/problem/11286

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

int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;

  // pair의 first를 기준으로, 
  // 절댓값이 가장 작은 원소가 우선순위 큐의 top에 위치함.
  // 출력할 때는 절댓값이 아닌 원래 값으로 출력
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

  int x;
  for (int i = 0; i < n; i++) {
      cin >> x;

      if (x == 0) {
          if (pq.empty())
              cout << "0\n";
          else {
              cout << pq.top().second << "\n";
              pq.pop();
          }
      }
      else {
          // 절댓값이 작을수록 top에 위치하도록
          pq.push({ abs(x), x });
      }
  }

  return 0;
}

연산자 오버로딩으로 구조체 정렬하기

학생의 학번이 작을수록 우선순위 큐의 top에 오도록 하려면 어떻게 해야 할까?

우선순위 큐는 내부적으로 힙으로 구현되어 있으며, 루트 노드에 최솟값이 오면 최소 힙, 최댓값이 오면 최대 힙이 된다.
우선순위 큐는 새로운 원소를 삽입할 때, 그 위치의 부모 노드와 크기를 비교하여 두 노드를 스왑할 것인지 결정한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나(최소 힙) 크면(최대 힙) 더 이상 스왑이 일어나지 않는다.
아래 연산자 오버로딩 코드에서, this->id가 부모 노드이고, s.id가 새로 삽입된 자식 노드이다. 만약 this.id > s.id 라면 true를 리턴하므로 스왑이 일어난다. 즉, 이 과정을 반복하다 보면 루트 노드에는 가장 작은 값이 위치하게 된다.

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

struct Student {
  int id;
  int math, eng;
  Student(int num, int m, int e) : id(num), math(m), eng(e) {}

  // 학번이 작을수록 top에 위치하도록
  bool operator < (const Student s) const {
      // 부모 노드가 자식 노드보다 크면 swap
      return this->id > s.id;
  }
};

int main() {
  priority_queue<Student> pq;

  // 학번이 가장 작은 원소가 top에 위치함.
  pq.push(Student(16, 100, 50));
  pq.push(Student(20, 60, 50));
  pq.push(Student(21, 80, 50));
  pq.push(Student(18, 90, 50));
  pq.push(Student(17, 70, 40));

  while (!pq.empty()) {
      Student s = pq.top();
      cout << "[학번, 수학 , 영어]: " << s.id << ' ' << s.math << 
				' ' << s.eng << '\n';
      pq.pop();
  }

  return 0;
}

[학번, 수학 , 영어]: 16 100 50
[학번, 수학 , 영어]: 17 70 40
[학번, 수학 , 영어]: 18 90 50
[학번, 수학 , 영어]: 20 60 50
[학번, 수학 , 영어]: 21 80 50

cmp 구조체 정의해서 정렬 기준 바꾸기

우선순위 큐 선언에 사용된 greater, less는 실제로 구조체이기 때문에, 이 부분에 사용자 정의 구조체를 넣으면 정렬 기준을 바꿀 수 있다.

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

struct Student {
  int id;
  int math, eng;
  Student(int num, int m, int e) : id(num), math(m), eng(e) {}
};

// 학번이 클수록 top에 위치하도록
struct cmp {
  bool operator() (Student a, Student b) {
      // 부모 노드가 자식 노드보다 작으면 swap
      return a.id < b.id;
  }
};

int main() {
  priority_queue<Student, vector<Student>, cmp> pq;

  // 학번이 가장 큰 원소가 top에 위치함.
  pq.push(Student(16, 100, 50));
  pq.push(Student(20, 60, 50));
  pq.push(Student(21, 80, 50));
  pq.push(Student(18, 90, 50));
  pq.push(Student(17, 70, 40));

  while (!pq.empty()) {
      Student ts = pq.top(); pq.pop();
      cout << "[학번, 수학 , 영어]: " << ts.id << ' ' << ts.math <<
				' ' << ts.eng << '\n';
  }

  return 0;
}