[C++]優先順位queueコンテナのデフォルトの使い方

34475 ワード
cpp テキストリンク
参考資料
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コンテナの1つであり、ヒップホップ資料構造によって内部的に実装される優先キューを使用することができる.はヘッダファイルに含まれます.
template class Container = vector,
class Compare = less>
class priority_queue;
  • 優先キューは、基本的にベクトルコンテナによって実現されるが、dequeueとともに使用することもできる.
  • ソート基準は基本的に降順(less)であるが、これも基準を変更する.
  • デフォルトジェネレータタイプ:priority queuepq;
  • 内部コンテナ変更:priority queuepq;
  • ソート基準の変更:優先順位queuepq;

    • 基本的な使い方

    #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;と宣言してもよいし、プッシュ要素から負の数に変換してもよい.優先キューのデフォルト値が最大値であるため、負の値では、スロットル値が最小の要素が昇順で出力され始めます.
    #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;
}

    演算子を使用したソート構造の再ロード


    生徒の学号を小さくしたいほど優先度Qのトップに入るにはどうすればいいのでしょうか.
    優先度キューの内部はhipによって実現され、ルートノードの値が最も高い場合は最小hip、値が最も高い場合は最大hipである.
    優先キューは、新しい要素が挿入されたときの親ノードとサイズを比較することで、2つのノードを交換するかどうかを決定します.親ノードのキー値が常に子ノードのキー値(最小ヒップ)より小さいか大きい場合は、交換されません.
    次の演算子リロードコードでは、this->idは親ノード、s.idは新しく挿入されたサブノードです.もしこれが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;
}
    [学号,数学,英語]:1610050
    [学号,数学,英語]:177040
    [学号,数学,英語]:189050
    [学号,数学,英語]:20 60 50
    [学号,数学,英語]:218050

    cmp構造を定義してソート条件を変更


    優先キュー宣言で使用されるgreat、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;
}
    Elasticsearch官方翻訳-2.6アップグレード
    Ubuntuシステムのバックアップとリカバリ