알고리즘 학습 #06 우선순위 큐

underlier12·2020년 1월 18일

알고리즘

목록 보기

6/17

06. 우선순위 큐

우선순위 큐의 필요성

우선 순위를 가진 데이터들을 저장하는 큐
데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나오는 특징
운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등에서 적용

우선순위 큐와 큐의 차이점

일반적인 형태의 큐는 선형
우선 순위 큐는 트리 구조(최대 힙으로 구현)

최대 힙(Max Heap)은 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리

최대 힙을 만족하는 트리

최대 힙이 아닌 트리

최대 힙의 루트 노드는 전체트리에서 가장 큰 값을 유지한다는 특징

우선 순위 큐의 삽입

삽입 후 루트 노드까지 값을 비교해 올라가면서 최대 힙을 구성 [상향식]

우선 순위 큐의 삭제

루트 노드를 삭제 후 가장 마지막 원소와 위치를 바꾼 뒤 값을 비교해 내려가면서 최대 힙 구성 [하향식]

우선 순위 큐의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_SIZE 10000

// 교환 함수
void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

// 우선 순위 큐
typedef struct {
	int heap[MAX_SIZE];
	int count;
} priorityQueue;

// 우선 순위 큐의 삽입
void push(priorityQueue* pq, int data) {
	if (pq->count >= MAX_SIZE) return;
	pq->heap[pq->count] = data;
	int now = pq->count;
	int parent = (pq->count - 1) / 2; 

	// 새 원소 삽입 후 상향식으로 힙 구성
	while (now > 0 && pq->heap[now] > pq->heap[parent]) {
		swap(&pq->heap[now], &pq->heap[parent]);
		now = parent;
		parent = (parent - 1) / 2;
	}
	pq->count++;
}

// 우선 순위 큐의 추출
int pop(priorityQueue* pq) {
	if (pq->count <= 0)return -9999; // 더 이상 추출할 것이 없을 경우
	int res = pq->heap[0]; // 루트 노드 값을 담아 둠
	pq->count--;
	pq->heap[0] = pq->heap[pq->count]; // 마지막 원소를 루트 노드로 넣음
	int now = 0, leftChild = 1, rightChild = 2;
	int target = now;

	// 새 원소 추출 후 하향식으로 힙 구성
	while (leftChild < pq->count) {
		if (pq->heap[target] < pq->heap[leftChild])target = leftChild;
		if (pq->heap[target] < pq->heap[rightChild] && rightChild < pq->count)target = rightChild;
		if (target == now) break; // 더 이상 내려가지 않아도 될 때 종료
		else {
			swap(&pq->heap[now], &pq->heap[target]);
			now = target;
			leftChild = now * 2 + 1;
			rightChild = now * 2 + 2;
		}
	}
	return res;
}

// main
int main(void) {
	int n, data;
	scanf("%d", &n);
	priorityQueue pq;
	pq.count = 0;
	
	for (int i = 0;i < n;i++) {
		scanf("%d", &data);
		push(&pq, data);
	}

	for (int i = 0;i < n;i++) {
		int data = pop(&pq);
		printf("%d ", data);
	}
	system("pause");
	return 0;
}