Concept
Priority Queue는 배열, 연결리스트, Heap 등으로 구현할 수 있다.
배열이나 연결리스트의 경우 삽입 또는 삭제시 마다 정렬이 필요, O(n) 시간이 걸릴 수 있으므로 Heap으로 구현하는게 효율적이다.
Binary Search Tree는 현재 노드 값보다 왼쪽 자식 노드 값이 더 작고 오른쪽 자식 노드 값이 더 큰 자료구조라면
Heap은 현재 노드 값이 자식 노드의 값보다 크기만 하면 된다.
삽입은 마지막 노드에서, 삭제는 루트 노드에서 이루어진다.
삭제시 두 자식 노드 중 큰 노드와 비교 및 교환을 하면 됨.
*삽입을 마지막 노드에서 하는 이유 : 최대한 트리 밸런스 유지 가능? -> 완전 이진 트리가 Heap의 조건!
Time Complexity
Worst Case
Balanced Tree가 아닌 이상 결국 일렬로 늘어질 수 있으므로 Tree의 시간복잡도는 O(n)
Average Case
트리의 높이만큼 O(log n)
Space Complexity
Worst Case
O(n)
Example
#include <stdio.h>
#include <stdlib.h>
#define ROOT 1
typedef struct _queue {
int *queue;
int lastIndex;
int size;
} PriorityQueue;
PriorityQueue *newPQ(int size) {
PriorityQueue *new = (PriorityQueue *)malloc(sizeof(PriorityQueue));
new->queue = (int *)calloc(size, sizeof(int));
new->lastIndex = 0;
new->size = size;
return new;
}
void put(PriorityQueue *pq, int value) {
if(pq->size-1 == pq->lastIndex) {
pq->queue = (int *) realloc(pq->queue, pq->size*2*sizeof(int));
}
int tmp;
int currentIndex = ++(pq->lastIndex);
pq->queue[currentIndex] = value;
while(currentIndex != ROOT) {
int parentIndex = currentIndex/2;
if(pq->queue[currentIndex] > pq->queue[parentIndex]) {
tmp = pq->queue[currentIndex];
pq->queue[currentIndex] = pq->queue[parentIndex];
pq->queue[parentIndex] = tmp;
currentIndex = parentIndex;
}
else break;
}
}
int pop(PriorityQueue *pq) {
if (pq->lastIndex == 0) return -1;
int value = pq->queue[ROOT];
int currentIndex = ROOT;
int tmp;
pq->queue[currentIndex] = pq->queue[pq->lastIndex];
pq->queue[pq->lastIndex] = 0;
(pq->lastIndex)--;
while(currentIndex <= pq->lastIndex) {
int left = pq->queue[currentIndex * 2];
int right = pq->queue[currentIndex * 2 + 1];
if (left > pq->queue[currentIndex] && left > right) {
tmp = pq->queue[currentIndex];
pq->queue[currentIndex] = left;
pq->queue[currentIndex*2] = tmp;
currentIndex = currentIndex * 2;
}
else if (right > pq->queue[currentIndex] && right > left) {
tmp = pq->queue[currentIndex];
pq->queue[currentIndex] = right;
pq->queue[currentIndex*2+1] = tmp;
currentIndex = currentIndex * 2 + 1;
}
else break;
}
return value;
}
int main() {
PriorityQueue *queue = newPQ(10);
for(int i=1;i<=100;i++) put(queue, i);
printf("%d ", pop(queue));
printf("%d ", pop(queue));
printf("%d ", pop(queue));
printf("%d ", pop(queue));
printf("%d ", pop(queue));
return 0;
}