자바 자료구조5 -우선순위 큐 사용법-

1. 우선순위 큐

 

큐가 먼저 들어오는 데이터가 먼저 나가는 선입선출 형식의 자료구조라면,

 

우선순위 큐는 항상 우선순위가 가장 높은 데이터에만 관심이 있고 이 데이터만 먼저 나갈 수 있는 형태의 자료구조

 

힙을 이용할때 삽입, 삭제, 탐색시간을 O(logN)으로 맞출 수 있어서 힙으로 보통 구현한다.

 

자바에서는 PriorityQueue라는 클래스를 사용할 수 있다.

 

import java.util.PriorityQueue;

 

PriorityQueue<(type)> (name) = new PriorityQueue<>(); 형태의 선언 필요

 

자바는 기본적으로 최솟값을 우선적으로 뽑아준다.

 

 

2. 핵심 메소드

 

2-1) add(E)

 

우선순위 큐에 데이터 E를 추가

 

2-2) size()

 

우선순위 큐에 들어있는 데이터 수를 반환

 

2-3) isEmpty()

 

우선순위 큐가 비어있다면 true, 아니라면 false를 반환

 

2-4) peek()

 

우선순위 큐에서 최솟값에 해당하는 데이터를 반환

 

2-5) poll()

 

최솟값에 해당하는 데이터를 반환하면서 우선순위 큐에서 그 값을 삭제

 

 

3. 최댓값을 뽑기

 

숫자에 -를 붙여 사용하는 트릭을 사용

 

-가 붙으면 최댓값에 해당하는 숫자가 가장 우선순위가 높아지며, 값을 넣기 전에 -를 붙여 넣고

 

값을 사용하기 전에는 -를 다시 붙여 사용하면 된다

 

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args){
        //정수를 관리할 priority_queue를 선언
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        pq.add(-2);
        pq.add(-9);
        pq.add(-5);
        
        System.out.println(-pq.peek()); //최댓값 9를 출력
        
        pq.poll(); //최댓값 9 제거
        
        System.out.println(pq.size());  //원소의 개수
        
        //가장 큰 값부터 순서대로 5,2 출력
        while(!pq.isEmpty()){
            System.out.println(-pq.poll());
        }
    }
}

 

4. 연습문제

 

1. push A: 정수 A를 우선순위 큐에 넣는 연산입니다.
2. pop: 우선순위 큐에서 최댓값을 제거하고, 그 값을 출력합니다.
3. size: 우선순위 큐에 들어있는 정수의 개수를 출력합니다.
4. empty: 우선순위 큐가 비어있으면 1, 아니면 0을 출력합니다.
5. top: 우선순위 큐에 들어있는 값 중 최댓값을 출력합니다.

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i = 0; i < n; i++){

            String q = sc.next();

            if(q.equals("push")){
                
                int A = sc.nextInt();

                pq.add(-A);

            } else if(q.equals("pop")){

                System.out.println(-pq.poll());
            } else if(q.equals("size")){
                System.out.println(pq.size());
            } else if(q.equals("empty")){
                
                if(pq.isEmpty() == true){
                    System.out.println(1);
                } else {
                    System.out.println(0);
                }
            } else {
                System.out.println(-pq.peek());
            }
        }
    }
}