우선순위 큐(Prioirity Queue) (1) - 최대 힙 이용

큐는 선입선출, 먼저 들어간 데이터가 먼저 나온다.
우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다. (우선순위가 다른 데이터 뿐만 아니라 같은 데이터가 존재할 수도 있다)

<구현 방법>

1. 배열을 기반으로 구현하는 방법
2. 연결리스트를 기반으로 구현하는 방법
3. 힙(heap)을 이용하는 방법

배열이나 연결리스트로 구현할 경우 간단하게 구현이 가능하지만, 데이터 삽입과 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 함.
또 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.
연결리스트의 경우, 삽입의 위치를 찾기 위해 첫번째 노드부터 시작해 마지막 노드에 저장된 데이터와 우선순위 비교를 진행해야 할 수도 있다. -> 성능 저하

그래서 일반적으로 힙을 이용해 구현한다.

1. 최대힙으로 구현하기

*최대힙이란?(max heap)
 -최대힙은 부모 노드가 자식노드 보다 값이 큰 완전 이진트리를 의미한다.
 -즉, 모든 부모 노드가 자식보다 값이 커야한다.
 -최대힙의 root node는 항상 최대값을 가진다.
 -전체 트리가 최대 힙 구조를 유지하도록 자료구조를 만들어야 한다.

1.1 우선순위 큐의 삽입

-삽입할 원소는 완전 이진트리를 유지하는 형태로 순차적으로 삽입된다.
-삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대힙을 구성한다.(상향식)
-즉, 부모노드와 비교를 해서 부모노드가 삽입한 노드의 값보다 작다면 교체한다.(logN의 시간복잡도를 가진다)

1.2 우선순위 큐의 삭제

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

먼저, 루트노드인 9를 삭제한다.

가장 마지막 원소를 루트 노드의 위치로 옮긴다.

이제 교체된 루트노드부터 하향식으로 내려가면서 최대 힙을 구성한다.(하향식)
현재노드보다 큰 값이 있으면 교체한다.

우선순위 큐 구현

우선순위 큐 정의

#include <stdio.h>
#define MAX_SIZE 10000

void swao(int *a, int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}

typedef struct priorityQueue{
	int heap[MAX_SIZE];
	int count;
}priorityQueue;

우선순위 큐의 삽입&&삭제

#include <stdio.h>
#define MAX_SIZE 10000

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

typedef struct priorityQueue{
	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;
 }
 
 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);
        }

        return 0;
}