우선순위 큐 삽입, 삭제 C로 구현하기

우선순위 큐는 '우선순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용된다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 최대힙은 부모가 자식보다 값이 큰 이진 트리를 의미한다

 

1. 우선순위 큐의 삽입

1) 배열 맨 끝에 삽입한다

2) 부모와 비교해서 swap을 한다. 가능하다면 루트까지 진행한다

3) 상향식 구조

 

2. 우선순위 큐의 삭제

1) 0번 인덱스를 추출한다

2) 맨 마지막 원소를 0번으로 넣는다

3) 하향식 구조로 자식들을 비교하면서 0번 인덱스의 기존 위치를 찾는다

 

#include <stdio.h>

#define SIZE 1000

typedef struct {
	int heap[SIZE];
	int count;
} PriorityQueue;

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void push(PriorityQueue* pq, int data) {
	if (pq->count >= SIZE) return;
	int now = pq->count;
	pq->heap[now] = data;
	int parent = (now - 1) / 2;

	while (now > 0 && pq->heap[now] > pq->heap[parent]) {
		swap(&pq->heap[now], &pq->heap[parent]);
		now = parent;
		parent = (now - 1) / 2;
	}

	pq->count++;
}

int pop(PriorityQueue* pq) {
	if (pq->count <= 0) return -1;
	int res = pq->heap[0];
	pq->count--;
	pq->heap[0] = pq->heap[pq->count];
	int now = 0, left = 1, right = 2;

	while (now <= pq->count) {
		int change = now;
		if (left <= pq->count && pq->heap[now] < pq->heap[left]) change = left;
		if (right <= pq->count && pq->heap[now] < pq->heap[right]) change = right;
		if (change == now) break;

		swap(&pq->heap[now], &pq->heap[change]);
		now = change;
		left = now * 2 + 1;
		right = now * 2 + 2;
	}

	return res;
}

int main(void) {
	PriorityQueue pq;
	pq.count = 0;

	push(&pq, 3);
	push(&pq, 2);
	push(&pq, 4);

	pop(&pq);
	for (int i = 0; i < pq.count; i++) {
		printf("%d ", pq.heap[i]);
	}
	printf("\n");
	return 0;
}