[algo] priority queue 정리

참고한 블로그: 바킹독의 알고리즘

정의와 구현

priority queue : 각 데이터마다 우선순위(Priority)가 부여되어 있어, 들어온 순서에 상관없이 우선순위가 가장 높은 데이터가 가장 먼저 나가는 자료구조

• heap 자료구조 사용하면
  - insert : O(lgN)
  - 우선순위 가장 높은 원소의 remove : O(lgN)
  - 우선순위 가장 높은 원소의 find : O(1)
• 배열 사용하면 각 O(1), O(N), O(N)
• 시간복잡도가 O(lgN)으로 비슷한데 set 말고 priority_queue 사용 이유? set 보다 수행 속도가 빠르고 공간을 적게 차지함
  - priority_queue 에는 트리에 불균형이 없음
  - set 에는 불균형 처리 관련 속도가 은근 시간 많이 차지함

heap 관련

• heap : 완전 이진 트리(Complete Binary Tree)를 기반으로 한 자료구조
  - min/max 값 빠르게 찾거나 priority queeue 구현시 사용됨
  - 특징1) 느슨한 정렬 상태 : 부모 노드와 자식 노드 간의 상하 관계만 따짐. 좌우 노드간 우선순위는 x. 즉 루트 노드는 min 혹은 max
  - 특징 2) 중복값 허용 : BST 와 다르게 중복값 허용
  - 특징3) 완전 이진 트리 : 리프노드 제외하고 모든 노드가 꽉 채워져 있어야 함 → 배열로 효율적 구현 가능
  - 참고) 왜 이진검색트리는 배열로 나타내기 어려운가?
• heap 을 배열로 구현하면
  - 부모 노드의 인덱스: 자식 인덱스 / 2
  - 왼쪽 자식 노드의 인덱스: 부모 인덱스 * 2
  - 오른쪽 자식 노드의 인덱스: (부모 인덱스 * 2) + 1
• 최소 힙에서는 min 값은 O(1)로 확인 가능하지만 max 나 10번째로 min 값 등은 쉽게 확인 x

#include <bits/stdc++.h>
using namespace std;

int heap[100005];
int sz = 0; // heap에 들어있는 원소의 수

void push(int x){
  heap[++sz] = x;
  int idx = sz;
  
  while(idx != 1){
    int par = idx/2;
    
    if(heap[par] <= heap[idx]) break;
    
    swap(heap[par], heap[idx]);
    idx = par;
  }
}

int top(){
  return heap[1];
}

void pop(){
  heap[1] = heap[sz--];
  int idx = 1;
  
  // 왼쪽 자식의 인덱스(=2*idx)가 size보다 크면 idx는 리프
  while(2*idx <= sz){
    int lc = 2*idx, rc = 2*idx+1; // 왼쪽 자식, 오른쪽 자식
    int min_child = lc; // 두 자식 중 작은 인덱스를 담을 예정
    
    if(rc <= sz && heap[rc] < heap[lc])
      min_child = rc;
      
    if(heap[idx] <= heap[min_child]) break;
    
    swap(heap[idx],heap[min_child]);
    idx = min_child;
  }  
}

int main(){
  push(10); push(2); push(5); push(9); // {10, 2, 5, 9}
  cout << top() << '\n'; // 2
  
  pop(); // {10, 5, 9}
  pop(); // {10, 9}
  cout << top() << '\n'; // 9
  
  push(5); push(15); // {10, 9, 5, 15}
  cout << top() << '\n'; // 5
  
  pop(); // {10, 9, 15}
  cout << top() << '\n'; // 9
  
  return 0;
}

STL priority_queue

https://en.cppreference.com/cpp/container/priority_queue

#include <bits/stdc++.h>
using namespace std;

int main(void){
  priority_queue<int> pq; // 최대 힙
  // priority_queue<int, vector<int>, greater<int>>로 선언시 최소 힙
  
  
  pq.push(10); pq.push(2); pq.push(5); pq.push(9); // {10, 2, 5, 9}
  cout << pq.top() << '\n'; // 10
  
  pq.pop(); // {2, 5, 9}
  cout << pq.size() << '\n'; // 3
  
  if(pq.empty()) cout << "PQ is empty\n";
  else cout << "PQ is not empty\n";
  
  pq.pop(); // {2, 5}
  cout << pq.top() << '\n'; // 5
  
  pq.push(5); pq.push(15); // {2, 5, 5, 15}
  cout << pq.top() << '\n'; // 15  
}

• priority_queue를 그냥 선언하면 기본적으로 최대 힙 → 최소 힙 선언 : priority_queue<int, vector<int>, greater<int>>로 선언