우선순위 큐(Priority Queue)란?
우선순위 큐(priority queue)
▶ 우선순위를 가진 항목들을 저장하는 큐(queue)
▶ FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.
| 자료구조 | 삭제되는 요소 |
| 스택 | 가장 최근에 들어온 데이터 (LIFO) |
| 큐 | 가장 먼저 들어온 데이터 (FIFO) |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
환자 치료의 예시를 들어보자.
▶ 큐: 먼저 온 사람을 먼저 치료
▶ 스택: 나중에 온 사람을 먼저 치료
▶ 우선순위 큐: 위급한 사람을 먼저 치료
우선순위 큐(priority queue)는 가장 일반적인 큐임.
스택(stack)이나 FIFO 큐를 우선순위 큐로 구현할 수 있다.
우선순위
▶ 시간: 스택, 큐
▶ 스택, 큐에서는 시간에 따라 자료구조를 조직화
▶ 다른 가치: 우선순위 큐
▶ 따라서 우선순위 큐는 스택이나 큐보다 일반적인 구조
▶ 키 (= 우선순위 값) 필드가 필요
우선순위 큐의 추상자료형 (Abstarct Data Type)
▶ 객체: n개의 element형의 우선 순위를 가진 요소들의 모임
▶ 연산
1) create(): 우선순위 큐를 생성한다.
2) init(q): 우선순위 큐 q를 초기화한다.
3) is_empty(q): 우선순위 큐 q가 비어있는지를 검사한다.
4) is_full(q): 우선순위 큐 q가 가득 찼는가를 검사한다.
5) insert(q, x): 우선순위 큐 q에 요소 x를 추가한다.
6) delete(q): 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
▶ 가장 중요한 연산은 insert 연산(요소 삽입), delete 연산(요소 삭제)이다.
▶ 우선순위 큐는 2가지로 구분
1) 최소 우선순위 큐
2) 최대 우선순위 큐
우선순위 큐 구현 방법
▶ 배열(array)을 이용한 우선순위 큐
▶ 연결리스트(linked list)를 이용한 우선순위 큐
▶ 히프(heap)를 이용한 우선순위 큐
먼저, 배열을 이용한 방법을 알아보자.
정렬된 배열(array)
▶ 우선순위를 기준으로 오름차순으로 정렬
▶ 가장 우선순위가 큰 데이터는 항상 배열의 마지막에 위치
삽입 함수
삽입 함수는 삽입 위치를 찾아야 함
▶ 일단 키 값을 기준으로 처음부터 삽입 위치까지 탐색. 시간 복잡도는 O(n)
▶ 해당 위치에 키 입력을 위한 데이터 이동 필요, O(n)
▶ 따라서 삽입 시, 시간 복잡도는 O(n)
삭제 함수
삭제 함수는 마지막 데이터를 리턴, 배열 데이터의 개수를 하나 줄임
▶ 삭제 시, 시간 복잡도는 O(1)
C언어로 구현해보자.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef int element;
typedef struct {
element data[MAX_SIZE];
int size;
} PriorityQueue;
// 우선순위 큐 초기화
void init_queue(PriorityQueue *pq) {
pq->size = 0;
}
// 우선순위 큐가 비었는지 확인
int is_empty(PriorityQueue *pq) {
return pq->size == 0;
}
// 우선순위 큐가 가득 찼는지 확인
int is_full(PriorityQueue *pq) {
return pq->size == MAX_SIZE;
}
// 우선순위 큐에 요소 삽입
void enqueue(PriorityQueue *pq, element item) {
if (is_full(pq)) {
fprintf(stderr, "큐가 포화상태입니다.\n");
return;
}
int i = pq->size - 1;
while (i >= 0 && pq->data[i] > item) {
pq->data[i + 1] = pq->data[i];
i--;
}
pq->data[i + 1] = item;
pq->size++;
}
// 우선순위 큐에서 요소 삭제
element dequeue(PriorityQueue *pq) {
if (is_empty(pq)) {
fprintf(stderr, "큐가 공백상태입니다.\n");
return -1; // 오류 값 반환
}
return pq->data[--pq->size];
}
// 우선순위 큐 출력
void print_queue(PriorityQueue *pq) {
for (int i = 0; i < pq->size; i++) {
printf("%d ", pq->data[i]);
}
printf("\n");
}
// 우선순위 큐 테스트
int main() {
PriorityQueue pq;
init_queue(&pq);
enqueue(&pq, 3);
enqueue(&pq, 1);
enqueue(&pq, 4);
enqueue(&pq, 1);
enqueue(&pq, 5);
enqueue(&pq, 9);
printf("Priority Queue: ");
print_queue(&pq);
printf("Dequeue: %d\n", dequeue(&pq));
printf("Dequeue: %d\n", dequeue(&pq));
printf("Priority Queue after dequeue: ");
print_queue(&pq);
return 0;
}
정렬 안된 배열(array)
정렬되지 않은 배열은 정렬된 배열과 비교하여 삽입과 삭제 함수에서 차이를 보인다.
삽입 함수
삽입 함수는 새로운 데이터를 무조건 배열 끝에 붙임
▶ 삽입의 시간 복잡도는 O(1)
삭제 함수
삭제 함수는 삭제할 데이터를 찾아야 함
▶ 삭제 시, 가장 높은 우선 순위를 처음부터 끝까지 뒤져야 함. 시간 복잡도는 O(n)
▶ 삭제 후, 데이터 이동 필요. 시간 복잡도는 O(n)
▶ 따라서, 삭제의 시간 복잡도는 O(n)
C언어로 구현해보자.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef int element;
typedef struct {
element data[MAX_SIZE];
int size;
} PriorityQueue;
// 우선순위 큐 초기화
void init_queue(PriorityQueue *pq) {
pq->size = 0;
}
// 우선순위 큐가 비었는지 확인
int is_empty(PriorityQueue *pq) {
return pq->size == 0;
}
// 우선순위 큐가 가득 찼는지 확인
int is_full(PriorityQueue *pq) {
return pq->size == MAX_SIZE;
}
// 우선순위 큐에 요소 삽입
void enqueue(PriorityQueue *pq, element item) {
if (is_full(pq)) {
fprintf(stderr, "큐가 포화상태입니다.\n");
return;
}
pq->data[pq->size++] = item;
}
// 우선순위 큐에서 최솟값 요소 찾기
int find_min_index(PriorityQueue *pq) {
if (is_empty(pq)) {
fprintf(stderr, "큐가 공백상태입니다.\n");
return -1; // 오류 값 반환
}
int min_index = 0;
for (int i = 1; i < pq->size; i++) {
if (pq->data[i] < pq->data[min_index]) {
min_index = i;
}
}
return min_index;
}
// 우선순위 큐에서 요소 삭제
element dequeue(PriorityQueue *pq) {
if (is_empty(pq)) {
fprintf(stderr, "큐가 공백상태입니다.\n");
return -1; // 오류 값 반환
}
int min_index = find_min_index(pq);
element min_value = pq->data[min_index];
// 삭제한 요소 뒤의 모든 요소를 한 칸 앞으로 이동
for (int i = min_index; i < pq->size - 1; i++) {
pq->data[i] = pq->data[i + 1];
}
pq->size--;
return min_value;
}
// 우선순위 큐 출력
void print_queue(PriorityQueue *pq) {
for (int i = 0; i < pq->size; i++) {
printf("%d ", pq->data[i]);
}
printf("\n");
}
// 우선순위 큐 테스트
int main() {
PriorityQueue pq;
init_queue(&pq);
enqueue(&pq, 3);
enqueue(&pq, 1);
enqueue(&pq, 4);
enqueue(&pq, 1);
enqueue(&pq, 5);
enqueue(&pq, 9);
printf("Priority Queue: ");
print_queue(&pq);
printf("Dequeue: %d\n", dequeue(&pq));
printf("Dequeue: %d\n", dequeue(&pq));
printf("Priority Queue after dequeue: ");
print_queue(&pq);
return 0;
}
정렬 안된 배열 VS 정렬된 배열
둘의 차이를 비교해보자.
▶ 정렬된 배열과 정렬 안된 배열을 사용할 때의 삽입, 삭제 효율이 서로 뒤바뀐 모습
▶ 삭제가 빨라야 한다면 정렬된 배열을 사용
▶ 삽입이 빨라야 한다면 정렬 안된 배열을 사용
▶ 삽입 삭제 전체를 감안하면 두 방법 모두 O(n)의 시간 복잡도이다.
그 다음, 연결 리스트를 이용한 우선순위 큐 구현 방법을 알아보자.
정렬된 연결 리스트(linked list)에 의한 구현
▶ 우선순위를 기준으로 내림차순으로 정렬
▶ 우선순위가 가장 높은 데이터를 헤드 포인터가 직접 가리킴
▶ 삭제의 시간 복잡도는 O(1)
▶ 삽입 함수는 키 값을 기준으로 삽입 위치를 찾아야 함.
▶ 삽입 위치가 마지막일 경우가 최악의 경우임. 시간 복잡도는 O(n)
▶ 배열처럼 이동은 불필요. 포인터만 변경하면 됨
▶ 삭제와 삽입 모두를 감안한 시간 복잡도는 O(1) + O(n) = O(n)이다.
C언어로 구현해보자.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct Node {
element data;
struct Node* next;
} Node;
typedef struct {
Node* head;
} PriorityQueue;
// 우선순위 큐 초기화
void init_queue(PriorityQueue* pq) {
pq->head = NULL;
}
// 우선순위 큐가 비었는지 확인
int is_empty(PriorityQueue* pq) {
return pq->head == NULL;
}
// 우선순위 큐에 요소 삽입
void enqueue(PriorityQueue* pq, element item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = item;
new_node->next = NULL;
// 정렬된 위치에 삽입
if (is_empty(pq) || pq->head->data > item) {
new_node->next = pq->head;
pq->head = new_node;
} else {
Node* current = pq->head;
while (current->next != NULL && current->next->data <= item) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
// 우선순위 큐에서 요소 삭제
element dequeue(PriorityQueue* pq) {
if (is_empty(pq)) {
fprintf(stderr, "큐가 공백상태입니다.\n");
return -1; // 오류 값 반환
}
Node* temp = pq->head;
element min_value = temp->data;
pq->head = pq->head->next;
free(temp);
return min_value;
}
// 우선순위 큐 출력
void print_queue(PriorityQueue* pq) {
Node* current = pq->head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 우선순위 큐 테스트
int main() {
PriorityQueue pq;
init_queue(&pq);
enqueue(&pq, 3);
enqueue(&pq, 1);
enqueue(&pq, 4);
enqueue(&pq, 1);
enqueue(&pq, 5);
enqueue(&pq, 9);
printf("Priority Queue: ");
print_queue(&pq);
printf("Dequeue: %d\n", dequeue(&pq));
printf("Dequeue: %d\n", dequeue(&pq));
printf("Priority Queue after dequeue: ");
print_queue(&pq);
return 0;
}
정렬 안된 연결 리스트(linked list)에 의한 구현
▶ 삽입될 데이터를 가장 첫 노드에 삽입. 시간 복잡도는 O(1)
▶ 배열처럼 이동은 불필요. 포인터만 변경하면 됨.
▶ 삭제를 위해 가장 큰 데이터를 처음부터 마지막까지 탐색해야 함. 탐색의 시간 복잡도는 O(n)
▶ 삭제와 삽입 모두를 감안한 시간 복잡도는 O(n) + O(1) = O(n)
C언어로 구현해보자.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct Node {
element data;
struct Node* next;
} Node;
typedef struct {
Node* head;
} PriorityQueue;
// 우선순위 큐 초기화
void init_queue(PriorityQueue* pq) {
pq->head = NULL;
}
// 우선순위 큐가 비었는지 확인
int is_empty(PriorityQueue* pq) {
return pq->head == NULL;
}
// 우선순위 큐에 요소 삽입
void enqueue(PriorityQueue* pq, element item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = item;
new_node->next = pq->head;
pq->head = new_node;
}
// 우선순위 큐에서 최솟값 요소 찾기
Node* find_min_node(PriorityQueue* pq) {
if (is_empty(pq)) {
return NULL;
}
Node* min_node = pq->head;
Node* current = pq->head;
while (current != NULL) {
if (current->data < min_node->data) {
min_node = current;
}
current = current->next;
}
return min_node;
}
// 우선순위 큐에서 요소 삭제
element dequeue(PriorityQueue* pq) {
if (is_empty(pq)) {
fprintf(stderr, "큐가 공백상태입니다.\n");
return -1; // 오류 값 반환
}
Node* min_node = find_min_node(pq);
element min_value = min_node->data;
// 최솟값 노드를 삭제
if (min_node == pq->head) {
pq->head = pq->head->next;
} else {
Node* current = pq->head;
while (current->next != min_node) {
current = current->next;
}
current->next = min_node->next;
}
free(min_node);
return min_value;
}
// 우선순위 큐 출력
void print_queue(PriorityQueue* pq) {
Node* current = pq->head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 우선순위 큐 테스트
int main() {
PriorityQueue pq;
init_queue(&pq);
enqueue(&pq, 3);
enqueue(&pq, 1);
enqueue(&pq, 4);
enqueue(&pq, 1);
enqueue(&pq, 5);
enqueue(&pq, 9);
printf("Priority Queue: ");
print_queue(&pq);
printf("Dequeue: %d\n", dequeue(&pq));
printf("Dequeue: %d\n", dequeue(&pq));
printf("Priority Queue after dequeue: ");
print_queue(&pq);
return 0;
}
각 구현 방법에 따른 성능을 비교해보자. (시간 복잡도)
| 표현 방법 | 삽입 | 삭제 |
| 정렬 안된 배열 | O(1) | O(n) |
| 정렬 안된 연결 리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결 리스트 | O(n) | O(1) |
| 히프 (heap) | O(logn) | O(logn) |
▶ n이 1000일 경우, O(n) 알고리즘은 1000초, O(logn) 알고리즘은 10초가 소요된다.
히프(heap)에 대해서는 다음 게시글에서 다뤄보도록 하겠다.
다음에 계속...