[JAVA] 우선순위 큐 (Priority Queue), 정렬 전략 설정법

우선순위 큐 란?

• 큐 자료구조는 선입선출(FIFO) 방식이지만
• 우선순위 큐는 들어간 순서와는 상관없이 높은 우선순위를 가진 원소가 먼저나온다는 특징을 가짐
• 숫자가 작을수록 먼저 나오는 큐를 최소힙 (Min Heap) 이라 하고,
• 숫자가 클 수록 먼저 나오는 큐를 최대힙 (Max Heap)이라 함

우선순위 큐 시간복잡도

• 삽입, 삭제 : O(log n)

우선순위 큐 선언 방법

// 낮은 수가 우선순위를 가짐
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 높은 수가 우선순위를 가짐
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

// 사전 순으로 더 빨리오는 문자열이 우선순위를 가짐
PriorityQueue<String> pq = new PriorityQueue<>();

기본 예제

• 숫자 10개를 입력받아 기본적인 우선순위 큐에 넣고 꺼내는 예제

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

public class priorityQueue {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PriorityQueue<Integer> pq = new PriorityQueue<>();

    System.out.print("입력 : ");
        for(int i = 0 ; i < 10 ; i ++) {
            pq.add(sc.nextInt());
        }

    System.out.print("출력 : ");
        for(int i = 0 ; i < 10 ; i ++) {
            System.out.println(pq.poll());
        }
    }
}

결과

입력 : 1 3 4 8 9 6 5 2 7 10
출력 : 1 2 3 4 5 6 7 8 9 10

• 실행 결과로 알 수 있듯이 우선순위 큐에 넣고 빼는 것 만으로도 정렬을 할 수 있음

정렬 전략 설정 예제 1

• 숫자 10개를 입력받아 오름차순으로 정렬하되, 홀수가 짝수보다 우선순위가 높다고 가정

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

public class priorityQueue {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        PriorityQueue pq = new PriorityQueue<>((o1, o2) -> {
            // 파라미터로 받은 o1, o2는 기본적으로 object 형이기 때문에
            // string으로 변환 후, int형으로 다시 변환
            int x = Integer.parseInt(o1.toString());
            int y = Integer.parseInt(o2.toString());

            // x, y가 들어왔을 때, x에 높은 우선순위를 주고싶다면 음수값 return
            if(x % 2 == y % 2) {
                return x - y;
            } else {
                if(x % 2 == 1 && y % 2 == 0) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });

    System.out.print("입력 : ");
        for(int i = 0 ; i < 10 ; i ++) {
            pq.add(sc.nextInt());
        }

    System.out.print("출력 : ");
        for(int i = 0 ; i < 10 ; i ++) {
            System.out.print(pq.poll() + " ");
        }
    }
}

결과

입력 : 1 2 3 4 5 6 7 8 9 10
출력 : 1 3 5 7 9 2 4 6 8 10

정렬 전략 설정 예제 2

• Integer 타입만을 받는 Priority Queue가 아닌 (Integer, Integer) 타입으로 받고, 첫번째 인자를 기준으로 정렬하는 예제

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

public class PriorityQueueTest {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        PriorityQueue<MyFormat> pq = new PriorityQueue<>();
        System.out.println("입력 x y : ");
        for(int i = 0 ; i < 5 ; i ++) {
             int x = sc.nextInt();
             int y = sc.nextInt();
             pq.add(new MyFormat(x, y));
        }

        System.out.println("출력 x y : ");
        for(int i = 0 ; i < 5 ; i ++) {
            MyFormat mf = pq.poll();
            System.out.println(mf.x + " " + mf.y);
        }
    }
    static class MyFormat implements Comparable<MyFormat>{
        int x, y;

        public MyFormat(int x, int y) {
            this.x = x;
            this.y = y;
        }

        // x를 기준으로 오름차순 정렬
        @Override
        public int compareTo(MyFormat o) {
            return this.x - o.x;
        }
    }
}

결과

• x를 기준으로만 정렬을 해주었기 때문에 y기준으로는 정렬을 하지 않고 들어오는 순으로 출력

입력 x y : 
3 7
4 1
2 8
8 6
4 0
입력 x y : 
2 8
3 7
4 1
4 0
8 6