반응형
SMALL
우선 순위 큐 구현입니다.
사실 우선 순위큐는 힙(Heap)을 이용해서 만들어진 자료구조인데요.
어떤 우선 순위를 기준으로 하느냐에 따라서 뽑아내는 순서를 달리할 수 있는 자료구조입니다.
힙은 배열을 기반으로 구현을 해야합니다. 물론 링크드 리스트로도 구현을 할 수 있습니다. 그렇다면 트리구조가 되겠죠. 허나 링크드 리스트로 구현 시 새로운 노르를 힙의 '마지막 위치'에 추가하는 것이 쉽지가 않습니다. 뭐 이렇게 설명만 한다면 사소한 문제 같지만, 이 문제를 해결하는 것보다 그냥 간단하게 배열로 접근해서 문제를 고민 안할 수 있다면, 배열을 쓰는게 낫겠죠?
자세한 것은 코드로 살펴보도록 하겠습니다.
SW expert Academy에서 코드를 가져왔는데 별로 좋은 코드는 아닌거 같습니다. 좀 더 직관적으로 짤 수 있을 부분을 난해하게 풀어냈네요.
#include <stdio.h>
#define MAX_SIZE 100
int heap[MAX_SIZE]; // heap의 최대 크기는 100입니다. index 범위는 0 ~ 99 입니다.
int heapSize;
void heapInit(void) {
heapSize = 0;
}
int heapPush(int value) {
if (heapSize + 1 > MAX_SIZE) { // 99까지는 if문에 걸려서는 안됩니다.
printf("queue is full");
return 0;
}
heap[heapSize] = value; // heap의 마지막 위치에 값을 우선 넣습니다.
int current = heapSize;
while (current > 0 && heap[current] < heap[current - 1] / 2) { // current가 0일 땐 부모 노드가 없으니 넘어갑니다. 비교를 할 땐 왼쪽이 자식노드, 오른쪽이 부모노드인데 부모노드가 더 클시 while문을 실행합니다.
int temp = heap[(current - 1) / 2]; // current에 - 1을 하는 이유는 heapSize를 0부터 세기 때문입니다.
heap[(current - 1) / 2] = heap[current]; // 부모노드와 자식노드를 바꿉니다.
heap[current] = temp;
current = (current - 1) / 2; // 반복적인 비교를 위해서 current의 값을 부모의 위치로 이동합니다.
}
heapSize++;
return 1;
}
int heapPop(int *value) {
if (heapSize <= 0) { // heapSize가 0이면 비어있는 상황입니다.
return -1;
}
*value = heap[0]; // root 노드의 값을 저장합니다.
heapSize--;
heap[0] = heap[heapSize]; // heap의 마지막 위치에 있는 값을 root 노드로 가져옵니다.
int current = 0; // root노드부터 시작합니다.
while (current * 2 + 1 < heapSize) { // 자식 노드가 있는 경우입니다.
int child;
if (current * 2 + 2 == heapSize) { // 현재 값의 오른쪽 값이 없는 경우에 child는 왼쪽값이 됩니다.
child = current * 2 + 1;
}
else {
child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2; // heap의 왼쪽값이 오른쪽값보다 더 작으면 child는 왼쪽값이 됩니다.
}
if (heap[current] < heap[child]) { // 부모노드의 값과 자식노드의 값을 비교해서 부모 노드가 더 작으면 break를 합니다.
break;
}
int temp = heap[current]; // 부모노드의 값과 자식노드의 값을 바꿉니다.
heap[current] = heap[child];
heap[child] = temp;
current = child; // 위치를 자식노드로 이동합니다.
}
return 1;
}
int main(void) {
int T, N;
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
scanf("%d", &N);
heapInit();
for (int i = 0; i < N; ++i) {
int value;
scanf("%d", &value);
heapPush(value);
}
for (int i = 0; i < N; ++i) {
int value;
heapPop(&value);
printf("%d ", value);
}
printf("\n");
}
return 0;
}
똑같지만 조금 더 직관적인 우선순위 큐 코드를 보도록 하겠습니다.
#include <stdio.h>
#define MAX_LEN 100
int arr[MAX_LEN];
int index = 0;
void HInsert(int value) {
int temp;
index++;
arr[index] = value; // 우선 끝에 값을 집어 넣습니다.
temp = index;
while (temp >= 1 && arr[temp / 2] > value) { // 부모 노드와 들어온 value를 비교합니다.
arr[temp] = arr[temp / 2]; // 부모노드가 더 크면 자식 노드를 부모 노드와 교체하고
temp = temp / 2; // 위치를 조정합니다.
}
arr[temp] = value; // while문을 다 돌고 나온 temp의 위치가 value의 위치입니다.
}
int HDelete(void) {
int result;
result = arr[1]; // root 노드의 값이 result 입니다.
int value = arr[index]; // 마지막의 값을 가져옵니다.
arr[index] = 0xffffff; // 뺏으면 초기화를 해줍시다.
index--;
int temp = 1;
while (value > arr[temp * 2] || value > arr[temp * 2 + 1]) { // 자식노드와 value의 값을 비교하여 value의 값이 더 크면 while문을 실행합니다.
if (arr[temp * 2] - arr[temp * 2 + 1] >= 0) { // 왼쪽이 더 크면
arr[temp] = arr[temp * 2 + 1]; // 오른쪽이랑 바꿉니다.
temp = temp * 2 + 1;
}
else { // 오른쪽이 더 크면
arr[temp] = arr[temp * 2]; // 왼쪽과 바꿉니다.
temp = temp * 2;
}
}
arr[temp] = value;
return result;
}
int main(void) {
int T, N;
scanf("%d", &T);
for (int t = 0; t < T; ++t) {
scanf("%d", &N);
arr[0] = -0xffffff; // 최소값이 root 값이 되어야 하기 때문입니다.
for (int i = 1; i < 100; ++i) {
arr[i] = 0xffffff; // 다른 값들은 큰 값들로 초기화 해줍시다.
}
for (int i = 0; i < N; ++i) {
int value;
scanf("%d", &value);
HInsert(value);
}
for (int i = 0; i < N; ++i) {
printf("%d ", HDelete());
}
printf("\n");
}
}
반응형
LIST
'C > 코드 리뷰' 카테고리의 다른 글
Linked List 구현하기 (2) (0) | 2020.01.29 |
---|---|
C언어 순열과 조합 (0) | 2020.01.11 |
큐 구현 (원형 큐) (0) | 2019.08.15 |
스택 구현 (0) | 2019.08.15 |
Linked List 구현하기 (1) (0) | 2019.06.23 |