우선순위 큐와 힙 개념 및 C++ STL

개념 출처 : chanhuiseok.github.io/posts/ds-4/

STL 출처 : chanhuiseok.github.io/posts/algo-54/

 

* 우선순위 큐

 - 우선순위가 높은 순서대로 pop하는 큐

 - 우선순위 큐는 배열이나 연결리스트로 구현하는 것보다

   힙으로 구현하는 것이 삽입 속도가 더 빠르므로, 힙으로 많이 구현함

 

* 복잡도 비교

 1) 삽입

   - 배열/연결리스트 : O(n)

   - 힙 : O(log₂n)

 2) 삭제

   - 배열/연결리스트 : O(1)

   - 힙 : O(log₂n)

 

* 삽입 방법

 1. 새로운 노드를 완전 이진 트리 구조를 유지할 수 있는 위치에 추가한다.

 2. 새로운 노드로부터 시작해서, 부모/자식 노드 간에 비교를 통해 swap을 반복한다.

 

* 삭제 방법

 1. 루트 노드를 삭제한다.

 2. 완전 이진 트리 구조를 유지하도록 마지막 노드를 루트 노드 자리에 옮긴다.

 3. 루트 노드로부터 시작해서, 부모/자식 노드 간에 비교를 통해 swap을 반복한다.

    (우선 순위가 높은 자식 노드와 swap)

 

* STL 사용법

 - #include <queue> 선언하여 사용

 - 주요 멤버 함수 : size(), empty(), push(), pop(), top()

priority_queue<int> pq; // 자료형만 썼을 때 아래와 같은 default 값이 적용된다.
priority_queue<int, vector<int>, less<int>> pq; // less than operator 사용

 - default가 최대힙(우선순위가 높을수록 큰 값)이다. 즉 less<int> (오름차순) 사용

 - 최소힙(우선순위가 높을수록 작은 값)을 사용하려면 greater<int> (내림차순) 사용

priority_queue<pair<int, int>> pq;
priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int,int>> pq;

- pair타입은 first를 기준으로 정렬됨