[JAVA] 우선순위 큐(Priority Queue)

[JAVA자료구조] 큐(Queue)에 대한 설명글 

[JAVA] 큐(Queue)

---

1. 우선순위 큐(Priority Queue)

모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력되는 구조입니다.

 

예를 들어, 운영체제에서 시스템 프로세스는 응용 프로세스보다 더 높은 우선순위를 가집니다.

 

우선순위 큐는 이러한 우선순위의 개념을 큐에 도입한 자료구조입니다.

 

1-1 우선순위 큐(Priority Queue) 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야 한다.) 

 

2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다. 

 

3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)이다.

 

4. 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰인다.

 

1-2 우선순위 큐(Priority Queue)의 선언

👆int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)

PriorityQueue priorityQueue = new PriorityQueue <>();

👆int형 priorityQueue 선언 (우선순위가 높은 숫자 순)

PriorityQueue priorityQueue = new PriorityQueue <>(Collections.reverseOrder());

👆String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)

PriorityQueue priorityQueue = new PriorityQueue <>();

👆String형 priorityQueue 선언 (우선순위가 높은 숫자 순)

PriorityQueue priorityQueue = new PriorityQueue <>(Collections.reverseOrder());

1-3 우선순위 큐(Priority Queue)의 추상 자료형

우선순위 큐는 우선순위를 갖는 요소들의 모임입니다.

연산은 큐와 동일합니다.

우선순위 큐에서도 가장 중요한 연산은 삽입과 삭제인데,

삭제연산에서 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어지지만,

특별한 언급이 없으면 우선순위 큐는 가장 높은 우선순위의 요소가 먼저 삭제되는 최대 우선순위 큐를 의미합니다.

1-4 우선순위 큐 ADT

• PriorityQueue() : 비어 있는 우선순위 큐를 만든다.
• isEmpty() : 우선순위 큐가 공백상태인지 검사한다.
• enqueue(e) : 우선순위를 가진 항목 e를 추가한다.
• dequeue() : 가장 우선순위가 높은 항목을 꺼내서 반환한다.
• peek() : 가장 우선순위가 높은 요소를 삭제하지 않고 반환한다.
• size() : 우선순위 큐의 모든 항목들의 개수를 반환한다.
• clear () : 우선순위 큐를 공백상태로 만든다.

 

2. 우선순위 큐의 삽입과 삭제

우선순위 큐의 삽입과 삭제

그림에서 항목들이 일렬로 나열되어 있지 않음에 유의해야 합니다.

 

우선순위 큐는 한순간에 가장 우선순위가 높은 항목만 알 수 있으면 됩니다.

 

나머지 자료를 순서대로 정렬하고 있을 필요가 없습니다.

 

따라서 선형 자료구조로 보기는 어렵습니다.

 

실제로 가장 효율적인 우선순위 큐의 구현 방법은 트리 구조를 사용하는

힙(heap)입니다.

 

2-1 우선순위 큐의 주요 응용

1. 허프만 코딩 트리를 만드는 과정
2. Kruskal의 최소비용 신장트리 알고리즘
3. Dijkstra의 최단거리 알고리즘
4. 인공지능의 A* 알고리즘

이제 우선순위 큐를 이용하는 문제를 통해 더 자세히 알아보도록 하겠습니다.

.
.

📝 문제

📎 백준 11286번- 절댓값 힙

11286번: 절댓값 힙

방법 1 - 메모리 : 27232KB , 시간 : 648ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Baek_11286 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // MyComparator 클래스의 객체 생성
        MyComparator mc = new MyComparator();
        // 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>(mc);
        int N = Integer.parseInt(bf.readLine());
        int input;
        for(int i=0; i<N; i++) {
            input = Integer.parseInt(bf.readLine());
            // 입력한 문자가 0 이 아니라면 큐에 저장
            if(input != 0) {
                pq.add(input);
                // 문자가 0 이라면
            } else {
                // 큐가 비어있지 않다면
                if(!pq.isEmpty()) {
                    // MyComparator에서 구현한 우선순위 큐로 꺼낸 수 출력
                    System.out.println(pq.poll());
                }
                // 배열이 비어있는데 절댓값이 가장 작은 값을 출력하라고 하는 경우 0을 출력
                else {
                    System.out.println(0);
                }

            }
        }
    }
}
// Comparator의 compare 메소드는 다음의 반환 값을 기반으로 두 객체를 비교합니다
//  양수:     첫 번째 객체 (o1)이 두 번째 객체 (o2)보다 크다는 것을 나타냅니다.
//  음수:     첫 번째 객체 (o1)이 두 번째 객체 (o2)보다 작다는 것을 나타냅니다.
//  0  :    두 객체 (o1과 o2)가 같다는 것을 나타냅니다.
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        int a = Math.abs(o1);
        int b = Math.abs(o2);
        // x = 0 일때
        // 절댓값이 작은 수를 출력
        if(a>b) {
            return 1;
        } else if (a<b) {
            return -1;
        }
        // 절댓값이 같다면 , 두 수중 음수를 출력해야 한다.
        else {
            // 두 수가 같다면 우선순위는 상관없다
            if(o1 == o2) {
                return 0;
                // o1 이 크다면 첫번째 수가 우선순위
            } else if (o1>o2) {
                return 1;
            }
            // o2가 크다면 두번째 수가 우선순위
            else {
                return -1;
            }
        }
    }
}

여기서 생소한 Comparator 에 대해서 짚고 넘어가보록 하겠습니다.

학교에서 배웠지만 역시 시간이 지나면 까먹어버리는 ,,

 

 

✅ comparator

Comparator는 Java에서 객체의 정렬 순서나 우선순위를 결정하기 위해 사용되는 인터페이스입니다. 기본적으로 객체들은 자신의 자연스

러운 순서로 정렬될 수 있지만, 사용자가 정의한 특별한 순서로 객체를 정렬하고 싶을 때 Comparator를 사용합니다.

✅ Comparator vs Comparable

Comparable: 객체가 자신을 다른 객체와 비교할 수 있게 해주는 인터페이스입니다. 즉, 객체의 자연스러운 순서를 정의합니다.

compareTo 메서드를 오버라이드해야 합니다.

 

Comparator: 두 객체를 비교하는 외부 도구. 특별한 순서나 여러 다른 순서로 객체를 정렬하고 싶을 때 유용합니다.

 

✅ 메소드

int compare(T o1, T o2):  두 객체 o1과 o2를 비교하고 결과를 반환합니다.

⭐️ 반환 값에 따라...

• 양수: o1이 o2보다 크다.
• 음수: o1이 o2보다 작다.
• 0: 두 객체는 동일하다.

// a>b 에서 "1" 을 반환한다면 ?
// a가 b 보다 우선순위가 낮다는 의미
// 큐에서 b 가 a 보다 앞에 위치한다.   ->  b a ....
    if(a>b) {
       return 1;
  	 }
         
// a>b 에서 "-1" 을 반환한다면 ?
// a가 b 보다 우선순위가 높다는 의미
// 큐에서 a 가 b 보다 앞에 위치한다.   -> a b ...
    else {
       return -1;
     }

.
.

방법 2 - 메모리 : 26712KB , 시간 : 632ms

-> 람다식 사용으로 방법 1보다 코드길이도 더 간결해지고 , 성능적으로 좀 더 좋다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Baek_11286 {
  public static void main(String[] args) throws IOException {
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(bf.readLine());

	  // 람다식
      PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)-> {
         int a = Math.abs(o1);
         int b = Math.abs(o2);
	    // 두 수의 절댓값이 같다면
         if(a == b) {
				// o1 이 o2 보다 크다면 1 반환 , 아니면 -1 반환
             return o1 > o2 ? 1 : -1 ;
         }
		// 절댓값이 같지 않다면 ?
         else {
			// 두 수의 차를 반환 
			// 양수면 a 가 큰값, 음수면 b가 큰값을 확인할 수 있다.
             return a - b;
         }
      });
      for(int i=0; i<N; i++) {
          int input = Integer.parseInt(bf.readLine());
         // 입력한 수가 0 이라면                        
          if(input == 0 ) {
               // 큐가 비어있다면 0을 출력                                     
              if(pq.isEmpty()) {
                  System.out.println("0");
              }
              // 큐에 수가 들어있는 상태면 위의 람다식에서 구현한 결과를 poll() 해주고 출력                                      
              else {
                  System.out.println(pq.poll());
              }
          }
          // 입력한 수가 0 이 아니라면
          // input 을 큐에 저장                                          
          else {
              pq.add(input);
          }
      }
  }
}

.
.

풀어볼 비슷한 문제 

📎 백준 1927번 최소 힙

1927번: 최소 힙

📎 백준 11279번 최대 힙

11279번: 최대 힙

 

오늘도 완료‼️