priority 에 대하 여큐 용기

quue 와 priorityqueue 용기 의 이해
quue 대기 열과 Stack 창고 의 구 조 는 매우 비슷 하 다. 그들 은 모두 하나의 결점 은 전구 결점 만 있 고 하나의 결점 은 후계 노드 만 있 으 며 나머지 결점 은 모두 전구 결점, 하나의 후계 노드 의 선형 표 가 있다.그들 두 사람 은 모두 똑 같이 불편 한 점 이 있다. quue 는 팀 끝 에 만 데 이 터 를 추가 하고 팀 머리 에서 데 이 터 를 삭제 할 수 있다.하지만 팀 헤드 와 팀 끝의 데 이 터 를 볼 수 있다.스 택 은 스 택 꼭대기 에 만 삽입 삭제 작업 을 할 수 있 습 니 다.
이 두 데이터 구 조 는 출력 이 매우 끊 기 는 문 제 를 만나면 매우 골 치 아 플 것 이다!하지만 우선 순위 가 있 습 니 다 priorityquue, 원래 대기 열 출력 이 어 려 운 문 제 를 바 꿀 수 있 습 니 다. 우선 대기 열과 대기 열의 차 이 는 우선 대기 열 이 입 대 된 순서대로 나 오 는 것 이 아니 라 대기 열 에 있 는 요소 의 우선권 순서에 따라 나 오 는 것 입 니 다.그러나 우선 대기 열의 난 제 는 원소 에 대한 우선권 이다.
우선 순위 대기 열 (priority quue) 은 0 개 이상 의 요소 의 집합 입 니 다. 모든 요 소 는 하나의 우선권 을 가지 고 있 습 니 다. 우선 순위 대기 열 에서 실 행 된 작업 은 (1) 검색 (2) 새 요 소 를 삽입 (3) 삭제 합 니 다.일반적으로 검색 작업 은 우선권 이 가장 큰 요 소 를 검색 하고 삭제 작업 은 이 요 소 를 삭제 하 는 데 사 용 됩 니 다.우선권 이 같은 요 소 는 선진 적 인 선착순 으로 처리 하거나 임 의 우선권 에 따라 진행 할 수 있다.바 텀 은 더미 로 이 루어 집 니 다. 그 복잡 도 는 push (): O (logn), pop (): O (logn), top (): O (1) 입 니 다.
어떻게 사용 합 니까?
1. 헤더 파일: \ # include < queue >
2、priority_queue 에서 원 소 를 어떻게 비교 합 니까?템 플 릿 설명 테이프 3 개 인자: priorityqueue, 그 중에서 Type 은 데이터 형식 이 고 Container 는 데 이 터 를 저장 하 는 용기 이 며 Functional 은 요소 비교 방식 입 니 다.Container 는 vector, deque 등 배열 로 이 루어 진 용기 여야 하지만 list 를 사용 할 수 없습니다.STL 에 서 는 기본적으로 vector 를 사용 합 니 다.비교 방식 Functional 은 기본적으로 operator 를 사용한다 "며" 따라서 뒤에 있 는 2 개의 매개 변 수 를 생략 하면 우선 대기 열 은 큰 꼭대기 (내림차 순) 이 고, 팀 헤드 요소 가 가장 크다. greater 는 숫자 가 작은 우선 순위 가 높다 는 것 을 나타 낸다.
다음은 큰 무더기 의 출력 을 시험 합 니 다:

#include 
#include
using namespace std;
int main()
{
     
    //     
    priority_queue<int> q;//         int，   vector，  less，            
    q.push(7);
    q.push(4);
    q.push(9);
    while(!q.empty()){
     
        cout<<q.top()<<" "; //      ，        
        q.pop();   //  9 7 4
    }
    return 0;
}

다음은 작은 출력 부터 큰 출력 까지:

#include 
#include
#include
using namespace std;
int main()
{
     
    //    
    priority_queue<int,vector<int>,greater<int> > q1; //      ，   vector     ，              ，
    q1.push(7);
    q1.push(4);
    q1.push(9);
    while(!q1.empty()) {
     
        cout<<q1.top()<< " ";
        q1.pop(); //  ：4 7 9
    }
    return 0;
}

위 는 STL 이 제공 하 는 모방 함수 greater < >, less < > 를 사용 하여 정렬 함 수 를 재 정의 하 는 과정 을 간소화 하 였 습 니 다. 기본 데이터 형식 대신 구 조 를 정의 하려 면 연산 자 를 다시 불 러 와 야 합 니 다.