우선 순위큐 와 힙
- 우선 순위큐 란?
우선순위 큐는 말 그대로 들어간 순서와 상관없이 우선순위가 높은 것을 먼저 뽑아내기 위해 만들어진 자료구조이며, 힙(Heap)이라고도 한다.
- 만약 둘의 차이를 따져보자면, 우선 순위 큐는 우선 순위가 높은 데이커가 먼저 나오는 자료구조 형태라고 할 수 있고, 힙은 완전 이진 트리 형태이며 자식 노드의 값보다 부모노드의 값이 크거나 같은 자료구조의 형태이다.
2. 우선 순위 큐 (힙의 특징) :
- 완전 이진 트리 구조의 형태를 갖는다.
- 일반적으로 배열로 구현한다.
- 일종의 반 정렬 상태를 유지한다. (느슨한 정렬 상태)
- 모든 노드에 저장된 값( 우선 순위 )들은 자식 노드의 것보다 우선 순위가 크거나 같다.
- 직접 연결된 자식과 부모 노드 간의 크기만 비교하면 된다.
- 힙으로 우선 순위 큐를 구현할 때에는 노드에 저장된 값을 우선 순위로 보면된다.
3. 최대힙과 최소 힙은 무엇인가 ?
먼저, 최대 힙(Max Heap)은 완전 이진트리면서, 루트 노드로 올라갈수록 저정된 값이 커지는 구조이다.
또한, 우선 순위도 값이 큰 순서대로 매긴다.
최소 힙 ( Min Heap)은 완전 이진 트리이며, 루트 노드로 올라갈 수록 저장된 값이 작아지는 구조이다.
마찬가지로, 우선 순위는 값이 작은 순서대로 매긴다.
만약 숫자 1 ~ 10을 저장하는 자료구조를 구현하려고 하는데 이 숫자들이 랜덤하게 삽입되고, 숫자가 클 수록 우선 순위가 크다고 가정할 때, 최대 힙에서는 10이 제일 먼저 꺼내지고, 그 뒤로 9 8,7,6,5 ... , 1 순으로 추출될 것이다.
이와 반대로, 최소 힙에서는 숫자가 작을 수록 우선 순위가 높다고 가정한다면, 1이 제일 먼저 꺼내지고, 그 후로 2, 3, ... , 10순으로 꺼내질 것이다.
4. 작동 방식
- 삽입
- 삽입하려는 값을 트리의 맨 마지막의 삽입한다.
- 부모 노드와 비교하면서 삽입하려는 값이 더 큰 경우에는 부모 모드와 값을 트레이드 한다.
- 삽입하려는 값보다 큰 값이 나오지 않을때까지 계속 반복한다.
- 만약 루트노드보다 삽입하려는 값이 큰 경우 루트노드에 저장한다.
- 삭제
- 트리의 맨 아래의 오른 쪽에 있는 원소인 pivot을 뿌리노드로 위치 시킨다.
- 왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 값과 비교한다.
- 자식 노드가 더 큰 경우에는 자식노드와 값을 바꾸어준다.
- pivot 값보다 작은 값을 만날 때 까지 계속 반복한다.
- 만약 leaf노드 까지 도달한 경우 pivot 값을 leaf 노드에 저장한다.
5. C++ 을 이용한 우선 순위 큐 구현
struct Heapdata
{
int priority; //우선 순위 값
int data; //데이터 값
};
class HeapArray
{
private:
int heapIndex;
int maxSize;
Heapdata* heapArray;
bool GetParentIndex(int index, int& returnindex);
bool GetLeftChildIndex(int index, int& indreturnindexex);
bool GetRightChildIndex(int index, int& returnindex);
bool GetPriorityChildIndex(int index, int& returnindex); //우선순위 높은 자식인덱스 반환
public:
HeapArray(int size = 10);
~HeapArray();
bool Insert(int priority, int data);
bool Delete(int& data);
void PrintAll();
};
6. 백준 1966번
#include <iostream>
#include <queue>
using namespace std;
int main() {
int count=0;
int test_case;
cin >> test_case;
int n, m,ipt;//문서의 개수, 궁금한 문서 위치, 중요도
for (int i = 0; i < test_case; ++i) {
count = 0;
cin >> n >> m;
queue<pair<int, int>> q;
priority_queue<int> pq; // 우선순위 큐
for (int j = 0; j < n; ++j) {
cin >> ipt;
q.push({ j, ipt });
pq.push(ipt);
}
while (!q.empty()) {
int index = q.front().first;
int value = q.front().second;
q.pop();
if (pq.top() == value) {
pq.pop();
++count;
if (index == m) {
cout << count << endl;
break;
}
}
else q.push({ index,value });
}
}
}