우선순위 큐(Priority Queue)를 알기 전에 큐(Queue)에 대해 다시 짚어보고 가자.
큐란 먼저 들어온 자료를 먼저 처리하는 FIFO(First In First Out)구조를 가지고 있는 자료구조를 말한다.
그러면 우선순위 큐란 뭘까? 기존의 큐 자료구조에 더해 우선 순위를 판별하는 값이 존재하는 자료구조를 말한다.
크게 와닿지 않으니 구현체 중 하나인 힙(Heap)을 예시로 들면 힙은 완전 이진 트리로 구성된 자료구조다.
완전 이진 트리란 마지막 리프 노드에 해당하는 깊이를 제외한 모든 노드가 빠짐 없이 채워져 있고 리프 노드에 해당하는 깊이에선 왼쪽부터 차례대로 채워지는 형태의 자료구조를 말한다. 아래 그림을 확인하자.
그럼 다시 돌아와서 힙을 예시로 우선순위 큐에 대해 알아보자.
우선순위 큐는 크게 두 가지 동작으로 이루어져 있다.
1. 값이 들어오면 우선순위 큐에 추가하며 up()을 수행한다.
void up(int x){
if(x / 2 == 0) return;
if(num[x] < num[x/2]){
int t = num[x]; num[x] = num[x / 2]; num[x / 2] = t;
up(x / 2);
}
}2. down()을 수행하며 큐의 값을 뺀다.
void down(int x){
int sw = k * 2;
if(sw > p) return;
if(sw + 1 <= p && num[sw] > num[sw + 1]) sw++;
if(num[x] > num[sw]){
int t = num[x]; num[x] = num[sw]; num[sw] = t;
down(sw);
}
}즉, 값이 들어오면 배열의 idx를 증가시키면서 값을 추가하고 up함수를 이용하여 up(idx)을 실행시키면 idx를 2씩 나눠가며 자신의 부모 인덱스의 값보다 자신의 값이 크다면 값을 바꿔주고 depth가 깊어진다.
(depth가 깊어지는 것과 다르게 idx는 2씩 나눈 몫을 가진다)
이제 값을 뺄 때의 상황을 알아보면 비어있으면 패스하고 비어있지 않은 경우 큐의 맨 앞에 있는 값을 맨 뒤에 있는 값으로 바꿔주고 down(1)을 실행한다.
출처
https://www.geeksforgeeks.org/difference-between-full-and-complete-binary-tree/
댓글