우선순위 큐(priority Queue)

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

데이터 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다.

큐는 선형적인 형태를 가지지만, 우선순위 큐는 트리 구조로 보아야하며, 최대 힙을 이용해 구현한다.

 

최대힙 : 부모 노드가 자식노드보다 값이 큰 완전 이진 트리

           루트 노드는 전체트리에서 가장 큰 값을 가지게 된다.

 

전체트리가 항상 최대힙 구조를 유지하도록 해야 우선순위 큐라고 말할 수 있다.

 

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

2. 삽입 이후, 루트노드까지 거슬러 올라가며 최대힙을 구성한다.

   -> logN의 시간복잡도를 가지게된다.

3. 삭제할 때 루트노드를 삭제하고, 마지막 원소를 루트 노드의 위치로 옮겨준다.

4. 삭제 후, 리프노드까지 내려가면서 최대 힙을 구성한다.

 

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

// 위치를 변경하기 위한 swap 함수
void swap(int *a, int *b){
	int temp = *a;
    *a = *b;
    *b = *temp;
}

typedef struct{
	int heap[MAX_SIZE];
    int count; // 힙에 들어있는 원소 개수, 인덱스로 생각
}priorityQueue;

//push 부분
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 ++ ;
}

//pop 부분
void pop(priorityQueue* pq, int data){
	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;
}

- 메인함수 구현

 

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;
}

큐의 삽입과 삭제는 logN의 시간복잡도를 가진다.

우선순위 큐를 이용한 정렬은 NlogN의 시간복잡도를 가지게 된다.