Priority queue (우선순위 큐) : 엔트리의 집합체를 저장하는 ADT.
- 엔트리 : key값과 value의 짝
- key가 우선 순위를 결정함
주요 메소드
- 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 |