우선순위 큐

우선순위 큐

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

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

 

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

  

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

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

 

최대힙(Max Heap)

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

  완전 이진트리는 자식노드가 2개씩 있거나 아예 없어야 한다.

 

  위 두 트리는 완전이진트리가 아니다.

  왼쪽 트리의 경우는 위에서 얘기했듯이 7의 자식노드가 하나밖에 없기 때문에 완전이진트리가 성립하지않고

  오른쪽 트리의 경우는 자식노드가 부모노드보다 크기때문에 성립하지 않는다.

  이렇게 완전이진트리가 아니라면 최대힙에 해당하지 않는다.

 

  최대힙의 루트노드는 전체트리에서 가장 큰 값을 갖는다는 특징이 있다.

  항상 전체트리가 최대힙 구조를 유지하도록 자료구조를 만들 수 있다.

  큐를 기반으로 하기 때문에 enQueue, deQueue로 정의한다.

  enQueue는 우선순위 큐에 데이터를 삽입.

  deQueue는 우선순위 큐에서 데이터를 추출하는 것이다.

 

우선순위 큐의 삽입

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

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

 

  위와 같은 처리과정으로 9를 상위노드와 비교해서 올려줌으로써 최대힙을 유지하도록 한다.

 

우선순위 큐의 삭제

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

  삭제이후에는 리프노드까지 내려가면서 최대힙을 구성한다. 하향식이다.

 

    루트노드를 삭제한 뒤 가장 하위 노드를 루트로 올려준다.

  루트노드의 하위노드중 더 큰값과 위치를 바꿔준다.

  바꿔준다음 또 그 하위 노드와 비교한다. 이 경우 1과 4를 하위노드로 갖기 때문에 더이상 내려가지 않는다.

 

예제코드

 

#define _CRT_SECURE_NO_WARNINGS
#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 enQueue(priorityQueue *pq, int data){
  if(pq->count >= MAX_SIZE) return;
  pq->heap[pq->count] = data;
  //count는 큐에 담겨있는 원소의 개수
  //제일 뒤로 데이터가 들어간다.
  
  int now = pq->count;
  //삽입된 데이터에 해당하는 인덱스를 now라고 정의.
  
  int parent = (pq->count - 1) / 2;
  //now에서 1을 빼고 2로 나누어진 값이 부모노드다.
  //3개층이 있는 완전 이진트리로 가정하면
  //오른쪽 최하단에 새로 들어오는 노드의 인덱스 6이다.
  //최하단 노드는 4개. 3 4 5 6 이기 때문에 
  //새로들어오는 노드의 부모노드 인덱스는 2가된다.
  //(6 - 1)/2 = 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++;
  //값이 새로 들어왔으니 count를 ++해준다.
}

int deQueue(priorityQueue *pq){
  //pq라는 매개변수로 큐를 받아서 처리
  
  if(pq->count <= 0) return -9999;
  
  int res = pq->heap[0];
  //루트노드를 담는다
  
  pq->count--;
  //삭제하는것이니 count를 1빼준다.
  
  pq->heap[0] = pq->heap[pq->count];
  //가장 마지막 노드를 루트노드에 넣어준다.
  
  int now = 0, leftChild = 1, rightChild = 2;
  int target = now;
  //target은 자기자신을 가리키도록 한다.
  //새 원소를 추출한 이후에 하향식으로 힙을 구성
  
  while(leftChild < pq->count){
    //leftChild가 카운트보다 작을때만 반복한다.
    //원소가 존재할때까지만 반복한다는 것이다.
    
    if(pq->heap[target] < pq->heap[leftChild]) target = leftChild;
    //target이 0이므로 root노드가 왼족 자식노드보다
    //작다면 둘을 바꿔주는 것이다.
    
    if(pq->heap[target] < pq->heap[rightChild] && rightChild < pq->count) target = rightChild;
    //루트노드가 오른쪽 자식노드보다 작고 오른쪽 자식노드가 카운트 보다 작다면
    //target을 rightChild로 바꾼다.
    //count보다 작다는 조건을 넣어놓는 이유는 인덱스를 벗어나는 경우를 방지하기 위해서다.
    //rightChild가 원소 개수보다 작을때에 한해서만 검사하도록 한다.
    
    if(target == now) break;
    //만약 두 자식노드보다 자기자신의 값이 더 크다면 이라는 조건이다.
    //target이 now가 된다는것은 위 조건문에서 false로 아무처리 되지 않고 그냥 내려왔기 때문에
    //가능한 것이므로 더이상 내려가지 않아도 된다는 것이다.
    //그럼 break로 빠져나가도록 한다.
    
    else{
      swap(&pq->heap[now], &pq->heap[target]);
      //자식노드가 더 크다면 변경해줘야 한다.
      //예를들어 leftChild가 더 큰 값이라 바꿔줘야 한다면
      //위 leftChild와 비교한 조건문에서 이미 target은 leftChild가 되었을 것이고
      //swap에서는 a와 b를 바꿔주므로 root인 now와 target인 leftChild의 순서가 바뀌게 된다.
      
      now = target;
      //아래로 더 체크해야 하기 때문에 now를 target으로 바꿔준다.
      
      leftChild = now * 2 + 1;
      rightChild = now * 2 + 2;
      //자리바꿈을 한 후에는 그 아래 노드들도 체크해야 하기 때문에 
      //now뿐만 아니라 두 자식노드의 값도 바꿔줘야 한다.
      //left로 내려왔다고 가정하고 보자면
      //now는 루트의 leftChild인 1이되고
      //leftChild는 1 * 2 + 1 = 3
      //rightChild는 1 * 2 + 2 = 4
      //이렇게 처리되어 1노드의 두 자식노드 인덱스가 된다.
    }
  }
  return res;
}

int main(void){
  int n, data;
  scanf("%d", &n);
  priorityQueue pq;
  pq.count = 0;
  //count를 0으로 초기화
  
  for(int i = 0; i < n; i++){
    scanf("%d", &data);
    enQueue(&pq, data);
  }
  
  for(int i = 0; i < n; i++){
    int data = deQueue(&pq);
    printf("%d ", data);
  }
  system("pause");
  return 0;
}

  위치를 잡고 설명하기 애매해서 대체로 주석처리했다.

  

  n은 데이터의 개수를 입력하는 것이고

  data에 값을 입력해서 넣어주면 큰수부터 작은수로 출력되는것을 확인할 수 있다.

  큰수부터 작은수로 출력되는것은 data = deQueue(&pq)인데 deQueue에서 반환되는 값은 res이고

  res는 heap[0]이기 때문에 가장 큰수부터 차례로 출력이 된다.

  가장 큰 수 부터 차례로 출력이 된다는 것은 제대로 처리가 되고 있다고 볼 수 있다.

 

  강의 볼 때는 몰랐었는데 정리하면서 출력이 이렇게 되는걸 늦게 알아서...

  한번만 추출하고 출력하거나 한번 반복할때마다 전체 출력하는 부분을 추가해봐야겠다.

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직