c++ priority_queue

가장 큰 숫자 3개, 가장 작은 숫자 4개를 골라라 같은 문제가 나오면

priority_queue를 사용하도록 하자.

 

Insertion, pop -> O(Logn)

Min or Max -> O(1)

Top이 Maximum 값

즉 Pop 하면 최대값이 없어지고 그다음 최대값이 Top으로 간다

 

Vector로 어떻게 Priority_Queue를 설정하는가

노드의 위치를 기반으로 인덱스를 설정해서 벡터에 넣는다

 

      9

   7     5 

 3 1

벡터에 9 7 5 3 1 순서로 입력한다.

L = 2*idx+1 이고

R = 2*idx+2 이다.

 

그리고 만약 새로운 값이 들어 오면 bubble 인덱스를 통해서 순서가 조정된다.

만약 pop 명령어로 최상단의 값이 사라지면 먼저 top 바로 밑에 있는 노드가 올라가게 되고,

노드간 비교를 통해서 제자리를 잡아간다.

 

코드 >>

#include <iostream>
#include <queue>
 
int main()
{
    std::priority_queue<int> q;
    q.emplace(1);
    q.emplace(3);
    q.emplace(5);
    q.emplace(7);
    q.emplace(9);
    std::cout << q.top() << std::endl;
    
    q.emplace(10);
    std::cout << q.top() << std::endl;
    q.pop();
    q.pop();
    q.pop();
    std::cout << q.top() << std::endl;
}