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

Dragony·2019년 12월 16일
3

자료구조

목록 보기
1/10
post-custom-banner

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

image.png

<구현 방법>

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

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

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

1. 최대힙으로 구현하기

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

1.1 우선순위 큐의 삽입

image(4).png

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

image(5).png

image(6).png

image(7).png

1.2 우선순위 큐의 삭제

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

먼저, 루트노드인 9를 삭제한다.
image(8).png

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

image(9).png

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

image(10).png

image(11).png

우선순위 큐 구현

우선순위 큐 정의

#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;
}
profile
안녕하세요 :) 제 개인 공부 정리 블로그입니다. 틀린 내용 수정, 피드백 환영합니다.
post-custom-banner

0개의 댓글