본문 바로가기

C/코드 리뷰

우선순위 큐 구현

반응형
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