C++ 우선순위 큐 사용법에 대한 자세한 설명

C++ 우선순위 큐 사용법에 대한 자세한 설명

우선순위 큐도 큐와 같은 일종의 데이터 구조입니다. 해당 작업은 대기열의 선입선출에만 국한되지 않고 논리적으로 수행될 수도 있습니다(최대값 또는 최소값에 따라 대기열 종료 등).

추천 학습: c++ 비디오 튜토리얼

일반 대기열은 선입선출 데이터 구조입니다. 요소는 대기열 끝에 추가되고 대기열의 헤드에서 삭제됩니다.

우선순위 대기열에서는 요소에 우선순위가 부여됩니다. 요소에 액세스하면 우선순위가 가장 높은 요소가 먼저 제거됩니다. 우선순위 큐는 선입, 최대 아웃의 행동 특성을 가지고 있습니다.

먼저 헤더 파일 #include578d2716abf2876f231498269846f87d를 포함시켜야 합니다. 큐와 다른 점은 데이터의 우선순위를 맞춤 설정할 수 있어 우선순위가 높은 데이터가 맨 앞에 큐에 들어가게 된다는 것입니다. 먼저 대기열에서 제거되었습니다.

우선순위 대기열은 대기열의 기본 작업을 포함하여 대기열의 모든 기능을 갖추고 있으며 이를 기반으로 내부 정렬을 추가합니다.

기본 작업은 대기열의 작업과 동일합니다.

top은 대기열의 헤드 요소에 액세스합니다.

대기열이 비어 있는지 여부는 비어 있습니다.

size는 대기열의 요소 수를 반환합니다.

push는 대기열에 요소를 삽입합니다. 대기열의 끝(및 정렬)

emplace 구성 요소가 대기열에 삽입됩니다

pop이 대기열의 헤드 요소를 팝합니다

swap이 콘텐츠를 교환합니다

정의: priority_queueab91b0b20a82ad8d07046f6e05e9fd7f

Type은 데이터 유형입니다. , Container는 컨테이너 형태(Container는 반드시 vector, deque 등의 배열로 구현된 컨테이너여야 하며, list는 사용할 수 없습니다. STL에서는 기본적으로 Vector를 사용함)이고, Functional은 비교 방식입니다.

사용자 정의 데이터 유형을 사용해야 하는 경우 이 세 가지 매개변수를 전달해야 합니다. 기본 데이터 유형을 사용할 때는 데이터 유형만 전달하면 됩니다. 기본값은 빅힙입니다.

일반적으로:

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

1. 기본 유형 우선순위 대기열의 예:

#include<iostream>
#include <queue>
using namespace std;
int main() 
{
    //对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    
    //      这里一定要有空格，不然成了右移运算符↓↓
    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

    for (int i = 0; i < 5; i++) 
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty()) 
    {
        cout << a.top() << &#39; &#39;;
        a.pop();
    } 
    cout << endl;

    while (!c.empty()) 
    {
        cout << c.top() << &#39; &#39;;
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty()) 
    {
        cout << b.top() << &#39; &#39;;
        b.pop();
    } 
    cout << endl;
    return 0;
}

실행 결과:

4 3 2 1 0
0 1 2 3 4
cbd abcd abc
请按任意键继续. . .

2 쌍을 우선순위 대기열 요소로 사용하는 예:

규칙: 쌍을 비교할 때 첫 번째를 비교합니다. 요소에서 첫 번째 요소는 두 번째 요소가 동일한지 비교합니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << &#39; &#39; << a.top().second << &#39;\n&#39;;
        a.pop();
    }
}

실행 결과:

2 5
1 3
1 2
请按任意键继续. . .

3. 우선 순위 대기열 요소로 사용자 정의 유형을 사용하는 예

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

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << &#39;\n&#39;;
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(b);
    f.push(c);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << &#39;\n&#39;;
        f.pop();
    }
}

실행 결과:

3
2
1
 
3
2
1
请按任意键继续. . .

위 내용은 C++ 우선순위 큐 사용법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!