알고리즘 study -19-

<우선순위 큐>

-> 원소를 제거할 시, 가장 우선순위가 높은 원소를 제거

<배열을 사용하는 경우>

#include <stdio.h>

const int MAX = 100;

struct  priorityQueue{
  int data[MAX];
  int len = 0;
  
  void push(int x){
    data[len++] = x;
  }
  
  void pop(){
    // 1. 우선순위가 가장 높은 원소 찾기
    // 2. 그 원소를 제거하고, 뒤의 원소를 당긴다
    
    int myMax = -9999999;
    int myMaxIdx = -1;
    
    // 최대값 / 최대값 인덱스 찾기
    for(int i = 0; i<len; i++){
      if(data[i] > myMax){
        myMax = data[i];
        myMaxIdx = i;
      }
    }
    
    // 땡기기
    for(int i = myMaxIdx; i < len; i++){
      data[i] = data[i+1];
    }
    
    len--;
  }
  
  int top(){
    
    int myMax = -999999;
     
    for(int i = 0; i<len; i++){
      
      if(data[i] > myMax){
        myMax = data[i];
      }
    }
    
    return myMax;
    
  }
};


int main() {
  
  priorityQueue myPQ;
  
  myPQ.push(1);
  myPQ.push(8);
  myPQ.push(7);
  myPQ.push(5);
  
  printf("%d\n", myPQ.top()); // 8
  
  myPQ.pop();
  
  printf("%d\n", myPQ.top()); // 7
  
  

  return 0;
}

위 코드의 경우 over/underflow는 편의상 고려 x
큰 값이 우선순위가 큰 것으로 가정

pop 을 하는 경우 우선순위가 큰 것을 찾는데 시간복잡도 O(n)

n이 100000이고 pop을 n만큼 하면 100000 * 100000로 매우 큰 시간복잡도

==>> 배열로 우선순위 큐 구현은 비효율적

==>> 더 효율적인 방법은???

<힙(Heap)>

• 부모의 값이 항상 자식보다 작은 완전 이진 트리

• 완전 이진 트리 ? = 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다

ex>

<완전 이진트리의 높이>

• 노드가 n개 == 높이가 log n !!

-> 힙에서 삽입 연산 시간 복잡도 -->> O(logn)
-> 삭제 역시 O(logn) : 트리 높이만큼 내려올 수 있으므로

<부모 & 자식 관계>

• 루트가 노드번호 1
• 특정 노드 번호가 n이면 부모 노드 번호는 n/2

<힙 삽입>

• 완전 이진 트리 형태를 만족하는 형태로 원소가 하나 추가된다
• 부모와 크기를 비교하면서 부모보다 작을 시 위치를 서로 바꾼다
• 부모 보다 크다면 멈춘다

<힙 삭제>

• 우선순위가 가장 높은 루트부터 삭제
• 루트 위치에 제일 마지막 노드를 올린다
• 현 상태에서 두 자식 중에 더 작은 것과 위치를 바꾸며 내려간다(힙 상태를 유지해야 하므로)

우선순위 큐는 배열보다 힙이 훨씬 더 효율적이다!!

배열 - 삽입 : O(1) / 삭제 : O(n)
힙 - 삽입 : O(logn) / 삭제 : O(logn)

<힙 구현>

#include <stdio.h>

const int MAX = 100;

struct PriorityQueue{
//       1
//    7     3
//  8  10   6  7    // 작을 수록 우선순위 높다고 가정
// 2 
  
  int data[MAX];
  int len = 1; // len은 맨 끝을 가리키고 있다 (추가 할 위치)
  
  
  void push(int x){
      data[len++] = x;
      
      int inx = len-1;  // 방금 새로 들어간 원소 위치
      
      while(inx > 1){  // root가 아닌 동안
      if(data[inx] < data[inx/2]){
        int temp = data[inx];
        data[inx] = data[inx/2];
        data[inx/2] = temp;
      }
      else
        break;
      
      inx = inx / 2;   // inx 값 업데이트  / 올라갔으므로
    }
  }
  
  void pop(){
    data[1] = data[len-1]; // 맨 끝값 루트로 올라간다
    data[len-1] = 0;
    len--;
    
    int inx = 1; // 루트에 넣어진 원소 위치
    
    while(1){
        // 1. 자식 중에서 우선순위 높은 것 알아내기
        // 2. 자신과 그 자식을 비교해서 자리 바꿀지 결정
        
      int pInx = -1; // 우선순위 높은 자식 노드 번호 담을 예정
      
      // (A )자식이 모두 없는 경우
      // (B) 왼쪽 자식만 존재하는 경우
      // (C) 양쪽 자식 모두 존재하는 경우
      
      if(len <= inx*2){  // 왼쪽 자식이x = 모두 없다
        break;
      }
      else if(inx*2 >= 1 && inx*2 < len 
      && len <= inx*2+1){ // 왼쪽 자식만 존재
        
        pInx = inx*2;
      }
      else{ // 양쪽 자식 모두 존재
        if(data[inx*2] < data[inx*2+1])
          pInx = inx*2;
        else
          pInx = inx*2+1;
      }
      
      // 자신과 자식 중 우선순위 높은 것 비교
      if(data[inx] > data[pInx]){
        int temp = data[inx];
        data[inx] = data[pInx];
        data[pInx] = temp;
        
        inx = pInx;
      }
      else{
        break; // 자식이 더 크므로 위치 그대로
      }
    }
  }
  
  int top(){
      return data[1]; // 루트 값 반환  // 우선순위 제일 높아서
  }
};

int main() {

  PriorityQueue myPQ;
  
  myPQ.push(3);
  myPQ.push(1);
  myPQ.push(2);
  
  printf("%d\n", myPQ.top()); // 1
  myPQ.pop();
  
  printf("%d\n", myPQ.top()); // 2
  myPQ.pop();
  
  printf("%d\n", myPQ.top()); // 3
  myPQ.pop();
  
  

  return 0;
}

힙은 우선순위가 큰 것을 빠르게 찾는다는 명확한 목적 존재!