[자료구조] Priority Queue 우선순위 큐

흔히 볼 수 있는 트리이다.

 

3 4 6 5 2 1 를 입력하였을 때

1 2 3 4 5 6 이 출력되도록 만들어 보겠다.

 

우선 Heap으로 만들어본 우선순위 Queue의 시간 복잡도는 O(logN) 정도 될 것이다.

아주 빠르다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_SIZE 10
#define parentNode(X) (X-1)/2
#define childNodeLeft(X) (X*2)+1
#define childNodeRight(X) (X*2)+2

int heap[MAX_SIZE];
int heapSize = 0;

void heapInit(void);
int heapIsFull(void);
int heapIsEmpty(void);
int heapPush(int value);
int heapPop(int* value);

int main(void)
{
	int a;

	int flag = 1;
	while (flag)
	{
		printf("HeapPush : 1, HeapPop : 2 를 입력하세요 :");
		scanf("%d", &a);
		switch (a)
		{
		case 1:
			printf("Push 할 값을 입력하세요 :");
			int b;
			scanf("%d", &b);
			if (heapPush(b)) printf("Push가 완료되었습니다.\n\n");
			else printf("Push에 실패하였습니다.\n\n");
			break;
		case 2:
			int c;
			if (heapPop(&c)) printf("Pop된 값은 %d 입니다.\n\n", c);
			else printf("Pop에 실패하였습니다.\n\n");
			break;
		default:
			printf("프로그램을 종료합니다.\n\n");
			flag = 0;
			break;
		}
	}
	return 0;
}

void heapInit(void)
{
	heapSize = 0;
}

int heapIsFull(void)
{
	return (heapSize + 1 > MAX_SIZE);
}

int heapIsEmpty(void)
{
	return (heapSize <= 0);
}

int heapPush(int value)
{
	if (heapIsFull() == 1) { printf("Heap Is Full!\n"); return 0; }

	heap[heapSize] = value; // 일단 heap의 맨 마지막에 넣음.

	int current = heapSize;
	while (current > 0 && heap[current] < heap[parentNode(current)]) // 현재 노드(자식노드)가 부모노드 보다 작은 경우에만 동작
	{
		int temp = heap[parentNode(current)];
		heap[parentNode(current)] = heap[current];
		heap[current] = temp; // 부모 노드와, 현재 노드(자식 노드)를 Swap 후
		current = parentNode(current); // 현재 노드(자식노드)를 부모노드로 바꿈.
	}

	heapSize = heapSize + 1; // heap은 1을 증가시켜서, 새로운 걸 받을 수 있도록.

	return 1;
}

int heapPop(int* value)
{
	if (heapIsEmpty() == 1) { printf("Heap Is Empty!!\n"); return 0; }

	*value = heap[0];
	heapSize = heapSize - 1;

	heap[0] = heap[heapSize];

	int current = 0;
	while (childNodeLeft(current) < heapSize) // 자식노드의 left가 heapSize보다 작을 경우에만 동작. 근데 왜 하필 left냐?
	{                                        // 이유는 right보다 먼저 입력되기 때문에, left가 없는데 right가 있는 경우는 없기 때문.
		int child;
		if (childNodeRight(current) == heapSize) { child = childNodeLeft(current); }
		else {
			if (heap[childNodeLeft(current)] < heap[childNodeRight(current)]) // 숫자가 작은게 우선순위가 높기 때문에
				child = childNodeLeft(current); // 왼쪽이 작으면 왼쪽을 선택
			else
				child = childNodeRight(current); // 오른쪽이 작으면 오른쪽을 선택
		}
		if (heap[current] < heap[child])
		{
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
	return 1;
}

 

 

일반적인 Queue는 FIFO 구조이다.

하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

상세한 설명은 chanhuiseok.github.io/posts/ds-4/ 를 참고하자.