우선순위 큐

우선순위 큐

정의와 성질

• 우선순위 큐: pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐
• 원소의 추가(Heap): O(lgN)
• 우선순위가 가장 높은 원소의 확인(Heap): O(1)
• 우선순위가 가장 높은 원소 제거(Heap): O(lgN)

  기능과 구현

• Heap은 이진 트리 모양을 가지고 있음
• 최소힙: 부모가 자식보다 작아야 함
• 최대힙: 부모가 자식보다 커야 함

  #include<iostream>
  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;
        }
        else{
            swap(heap[par],heap[idx]);
            idx=par;
        }
    }
  }
  int top(){
    return heap[1];
  }
  void pop(){
    heap[1]=heap[sz--];
    int idx=1;
    // 왼쪽 자식의 인덱스가 sz보다 크면 idx는 리프
    while(2*idx<=sz){
        int lc=2*idx; //왼쪽 자식
        int 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;
    }
  }
  void test(){
    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
  }
  int main(void){
    test();
    return 0;
  }
  

  STL

• Priority_Queue

  #include<iostream>
  #include<vector>
  #include<queue>
  #include<functional>
  using namespace std;
  int main(void){
    priority_queue<int> pq;// 최대 힙
    priority_queue<int, vector<int>,greater<int>> spq;// 최소힙
    pq.push(10);
    pq.push(2);
    pq.push(5);
    pq.push(9);// {10,2,5,9}
    spq.push(10);
    spq.push(2);
    spq.push(5);
    spq.push(9);// {10,2,5,9}
    cout<<pq.top()<<'\n';// 10
    cout<<spq.top()<<'\n';// 2
    pq.pop();// {2,5,9}
    spq.pop();// {10,5,9}
    cout<<pq.size()<<'\n';// 3
    cout<<spq.size()<<'\n';// 3
    return 0;
  }
  

  Tip

• Priority_queue에서 할 수 있는 것은 set에서도 모두 가능하고 시간복잡도도 동일한데 priority_queue를 사용하는 이유는?
  • Priority_Queue는 set보다 수행 속도가 빠르고, 공간도 적게 차지함
  • set은 새 정점을 동적할당하거나 정점을 제거하고 불균형이 발생할 때 그것에 대한 처리가 필요함
  • Prioirty_Queue는 트리 자체가 불균형이 없고 무조건 lgN만큼 비교하면서 자리를 바꾸기 때문에 빠름