[자료구조] 우선순위 큐

우선순위 큐란?

• 기본적으로 큐 구조이기에 First-in First-out
• 그러나 일반적인 큐와는 다르게 입력되는 데이터 순서대로가 아닌, 우선순위가 높은 것을 먼저 꺼내기 위해 만들어진 자료구조
• 큰 것에 우선순위를 주는 것을 최대힙(Max Heap)이라 한다
• 작은 것에 우선순위를 주는 것을 최소힙(Min Heap)이라 한다 => 기본설정
• 시간 복잡도는 n*logn

---

실전! 문제 풀이(백준 11286)

import java.util.*;
import java.io.*;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->{
                               int first_abs = Math.abs(o1);
                               int second_abs = Math.abs(o2);
                               if(first_abs == second_abs){
                                   return o1-o2;
                               }                            
                               return first_abs - second_abs;});
        
        for(int i=0; i<n ;i++){
            int select = Integer.parseInt(br.readLine());
            if(select==0){
                if(queue.isEmpty()){
                    System.out.println("0");
                }else{
                    System.out.println(queue.poll());
                }    
            }else{
                queue.add(select);
            }
        }
    }
}

얻어갈 점:

• Scanner는 입력값이 별로 없을때, BufferedReader는 입력값이 많을때 좋음
• 문제를 읽어보면 힙이라는 단어 + 절대값에 따라 정렬되는 것을 종합하면 우선순위 큐를 사용하는 것을 알 수 있음
• 우선순위 큐는 기본 설정시 최소힙구조를 가지나, 우선순위(정렬)를 커스터마이징해서 사용할 수 있다
• PriorityQueue <.Integer>queue = new PriorityQueue<>((o1,o2)->{
  int first_abs = Math.abs(o1);
  int second_abs = Math.abs(o2);
  if(first_abs == second_abs){
  return o1-o2;
  }
  return first_abs - second_abs;});
• 위의 코드에서 람다식을 활용하여 우선순위(무엇을 기준으로 우선순위를 주어 정렬할지)를 정의해줬는데 주어진 파라미터가 (o1,o2)일 때 o1-o2를 하게되면 기본 설정과 같이 최소 힙을, o2-o1을 하면 반대로 최대 힙을 가지게 할 수 있다.
• 정리하자면 앞에 값에서 뒤에 값을 빼면 최소 힙 / 뒤에 값에서 앞에 값을 빼면 최대 힙