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;

};

 

'DataStructure' 카테고리의 다른 글

[자료구조] Priority Queue : Heaps  (0) 2022.05.30
[자료구조] Trees  (0) 2022.05.06
[자료구조] Lists  (0) 2022.04.17
[자료구조] Vector  (0) 2022.04.16
[자료구조] 알고리즘 분석  (0) 2022.04.16

+ Recent posts