[자료구조] Priority Queue

Priority queue (우선순위 큐) : 엔트리의 집합체를 저장하는 ADT.

•   엔트리 : key값과 value의 짝
•   key가 우선 순위를 결정함
  
  

출처 : https://favtutor.com/resources/images/uploads/Priority_Queue_c++.png

주요 메소드

• insert(e) : 엔트리 e 삽입
• pop() : 가장 우선순위가 높은 값 삭제

 

부가 메소드

• top() : 가장 우선순위가 높은 값 출력
• size(),empty()

 

구현 방법 

• unsorted list( selection-sort, 선택정렬 ) : 우선순위 대로 저장 되어 있지 않다가 pop할때 정렬하여 출력
• sorted list( insertion-sort, 삽입정렬 ) : insert할 때 부터 정렬하여 저장
• heap : binary tree 형식으로 저장

 

Unsorted list ( 선택정렬 )

• insert -> O(1)
  n개의 엔트리를 insert 하면 -> O(n)
• pop, top -> O(n)
  n개일 때 부터 1개일 때 까지 pop -> n + n-1 + ... + 2 + 1 = n(n+1)/2 -> O(n^2)

class unsortedSeqPQ {
public:
    int size() {
        return seq.size();
    }
    bool empty() {
        return size() == 0;
    }
    void insert(int e) {
        seq.push_back(e);
    }
    int min() {
        if (empty()) return -1;

        compare C;
        int minVal = seq[0];

        for (int i = 0; i < seq.size(); i++) {
            if (C(seq[i], minVal)) {
                minVal = seq[i];
            }
        }
        return minVal;
    }
    void removeMin() {
        if (empty()) return;
        compare C;
        int minIdx = 0;

        for (int i = 0; i < seq.size(); i++) {
            if (C(seq[i], seq[minIdx])) {
                minIdx = i;
            }
        }

        seq.erase(seq.begin() + minIdx);
    }
private:
    vector<int>seq;

};

Sorted list ( 삽입정렬 )

• insert -> O(n)
  저장할때 부터 우선순위에 맞춰서 저장
• pop,top -> O(1)
  우선순위 대로 pop하므로 상수시간 소요

class sortedSeqPQ {
public:
    int size() {
        return seq.size();
    }
    bool empty() {
        return size() == 0;
    }
    void insert(int e) {
        compare C;
        int idx = 0;
        for (idx = 0; idx < seq.size(); idx++) {
            if (C(seq[idx], e)) break;
        }
        seq.insert(seq.begin() + idx, e);
    }
    int priority() {
        if (empty()) return -1;
        return seq.back();
    }
    void removePriority() {
        if (empty()) return;
        seq.pop_back();
    }
private:
    vector<int>seq;

};