POJ - 데이터 구조 - 우선 대기 열 템 플 릿

2810 단어
우선 대기 열 템 플 릿
우선 대기 열 은 더미 로 이 루어 지기 때문에 우선 대기 열 에 있 는 push (), pop () 작업 의 시간 복잡 도 는 모두 O (nlogn) 입 니 다.
우선 대기 열의 초기 화 는 세 개의 인자 가 필요 합 니 다. 요소 유형, 용기 유형, 비교 연산 자 입 니 다.
익숙 한 우선 대기 열 작업 이 필요 합 니 다:
  • q. top () 액세스 더미
  • q. push () 입 적
  • q. pop () 출 로
  • 유형 별 요소 의 우선 순위 설정
  • 정의 더 미 는 마지막 두 개 > > 사이 에 빈 칸 이 있 습 니 다
  • 데이터 구조
    priority_queue < int, vector<int>, less<int> > q; //    ——     
    priority_queue < int, vector<int>, greater<int> > q; //    ——     

    예 - 백 련 4078: 퇴적 구조 실현
    AC 코드
    #include
    #include
    #include
    #include
    
    using namespace std;
    
    int main()
    {
        priority_queue < int, vector<int>, greater<int> >q;
        int m, t, x, top;
        cin >> m;
        while (m--)
        {
            cin >> t;
            if (t == 1)
            {
                cin >> x;
                q.push(x);
            }
            if (t == 2)
            {
                top = q.top();
                cout << top << endl;
                q.pop();
            }
        }
        return 0;
    }

    좋은 웹페이지 즐겨찾기