priority_queue

[devLupin]

priority_queue(pq)는 자료구조 중 하나로, C++에서는 queue에 구현되어 있음.

• pq는 default가 max heap 이다.
  • 큰 게 먼저 뽑힌다는 뜻
• operator 오버로딩, 함수 오버로딩 등의 방법을 주로 쓰지만,
• 간단한 int 자료형 정렬 시 ~(bitwise-not)를 사용할 수 있다.

priority_queue<int> maxPQ;
priority_queue<int, vector<int>, greater<int>> minPQ;

// 다음과 같이 대체 가능하다.
priority_queue<int> pq;

pq.push(-num);
-pq.top();

// 그러나 마이너스 보다는 bitwise-not
pq.push(~num);
~pq.top();

• bitwise-not을 쓰는 이유는 굉장히 명료하다.

  • 자료형의 범위의 절대값은 1의 차이가 있다.
  • int의 범위는 4바이트일 경우 -2147483648부터 2147483647까지
  • 2147483648을 우선순위 큐에 넣을 때 음수를 붙이는 순간 signed integer overflow가 발생한다.

• 해당 내용은 알고리즘 스터디에서 Yun님에게 얻은 정보이다!

• 더 자세한 내용은 블로그에 명시되어 있다.

[devLupin]

Operator overoading

• operator()

typedef struct Compare{
    bool operator()(int a, int b) {
        return a > b;
    }
};

priority_queue<int, vector<int>, Compare> pq;

• operator<()

typedef struct Node {
    int x, y;

    Node(int x, int y) { this->x = x, this->y = y; }

    bool operator<(const Node& tmp) const {
        if (x == tmp.x)
            return y < tmp.y;
        return x < tmp.x;
    }
};

priority_queue<Node> pq;