우선순위 큐 (Priority Queue)

우선순위 큐

큐는 선입선출(First In First Out) 자료구조이지만

우선순위 큐는 들어온 순서가 아닌 정의된 우선순위에 따라 먼저 처리되는 구조이다.

ex) 수행할 작업이 여러개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행

 

※ 여러 자료구조들로 구현할 수 있으나 heap 특성과 많이 닮아 heap으로 구현하는 경우가 많다.

    ex) 연결 리스트나 배열에 원소들을 집어넣고,

         원소를 꺼낼 때마다 모든 원소를 순회하며 우선순위가 가장 높은 원소를 찾는 방법

 

▶ [그래프] 힙(Heap) 자료구조란?

▶ [큐] Queue란?

▶ [STL] Priority_queue

힙(Heap) 자료구조란?

[큐] Queue란?

[C++] [STL] Priority_queue

구현 예시

const int LM = 20010;
bool Max(int a, int b) { return a > b; }
bool Min(int a, int b) { return a < b; }
void swap(int& a, int& b) {
       int t = a; a = b; b = t;
}
typedef struct PriorityQueue PQ;
struct PriorityQueue {
       int heap[LM];
       int hn;
       bool (*comp)(int a, int b);
       void init(int sign) {
              hn = 0;
              comp = sign ? Max : Min;
       }
       int top() { return heap[1]; }
       int size() { return hn; }
       bool empty() { return hn == 0; }
       void push_heap(int num) {
              heap[++hn] = num;
              int c = hn;
              for (; c > 1 && comp(heap[c], heap[c / 2]); c /= 2)
                     swap(heap[c], heap[c / 2]);
       }
       int pop_heap() {
              int p = 1, c = 2, ret = heap[1];
              swap(heap[1], heap[hn--]);
              for (; c <= hn; p = c, c *= 2) {
                     if (c < hn && comp(heap[c + 1], heap[c])) c++;
                     if (!comp(heap[c], heap[p])) break;
                     swap(heap[c], heap[p]);
              }
              return ret;
       }
}maxpq, minpq;

　

 

[구현 예시] template 버전

const int LM = 20010;
template<class T>
bool Max(T& a, T& b) { return a > b; }
template<class T>
bool Min(T& a, T& b) { return a < b; }
template<class T>
void swap(T& a, T& b) {
    T t = a; a = b; b = t;
}
template<class T>
struct PriorityQueue {
    T heap[LM];
    int hn
        ;
    bool (*comp)(T& a, T& b);
    void init(int sign) {
        hn = 0;
        comp = sign ? Max<T> : Min<T>;
    }
    T top() { return heap[1]; }
    int size() { return hn; }
    bool empty() { return hn == 0; }
    void push_heap(int num) {
        heap[++hn] = num;
        int c = hn;
        for (; c > 1 && comp(heap[c], heap[c / 2]); c /= 2)
            swap(heap[c], heap[c / 2]);
    }
    T pop_heap() {
        int p = 1, c = 2;
        T ret = heap[1];
        swap(heap[1], heap[hn--]);
        for (; c <= hn; p = c, c *= 2) {
            if (c < hn && comp(heap[c + 1], heap[c])) c++;
            if (!comp(heap[c], heap[p])) break;
            swap(heap[c], heap[p]);
        }
        return ret;
    }
};

 

Reference

- [BOJ] 11651 좌표 정렬하기 2

- [BOJ] 1966 프린터큐

- [BOJ] 15972 물탱크