[자료구조] 우선순위 큐

우선순위 큐는 '우선 순위'를 가진 데이터들을 저장하는 큐를 의미한다.

데이터를 꺼낼 때 우선 순위가 높은 데이터가 먼저 나온다는 특징이 있어서 많이 활용되고 있다.

우선순위 큐는 운영체제의 작업스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 

우선순위 큐의 시간복잡도는 O(NlogN)이다.

 

일반적인 형태의 큐는 선형적인 형태를 가지고 있지만 우선순위 큐는 트리(Tree) 구조로 보는 것이 합리적이다. (완전이진트리와 흡사)

일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 

 

최대 힙(Max Heap)

부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다. 

전체 트리에서 루트 노드가 가장 큰 값을 가진다. 

 

우선순위 큐의 삽입

- 완전 이진 트리를 유지하는 형태로 순차적으로 삽입된다.

- 삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대 힙을 구성한다. [상향식]

- 삭제를 할 때는 루트 노드를 삭제하고, 가장 마지막 원소를 루트 노드의 위치로 옮겨준다. 삭제 이후에는 리프 노드까지 내려가면서 최대 힙을 구성한다. [하향식]

 

우선순위 큐 구현

#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;
}
//-------------우선순위 큐의 사용 push, pop-------------//

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)l
    }
    system("pause");
    return 0;
}