PriorityQueue() 사용법

ps에서 우선순위 큐는 최단거리 알고리즘(다익스트라 알고리즘)에 많이 사용되며, 구현 문제에도 사용될 수 있다

최댓값 혹은 최솟값 꺼내서 처리한 뒤 다시 넣고.. 이렇게 반복하는 종류의 문제들에서 잘 쓰인다

 

 

ㅇPriorityQueue(): 입력 요소에 우선순위를 부여

e.g. 입력[3, 1, 5, 2, 4] -> 출력[1, 2, 3, 4, 5]

 

기본 설정이 최소 힙(min-heap)으로 되어있기 때문에 오름차순으로 출력된다

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(3);
        pq.add(1);
        pq.add(5);
        pq.add(2);
        pq.add(4);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

 

 

 

+ 우선순위를 다르게 설정하는 법: Comparator 인터페이스 이용

e.g. 내림차순으로 큰 요소부터 먼저 출력하려는 의도 - Comparator.reverseOrder()

import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueDescendingExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        pq.add(3);
        pq.add(1);
        pq.add(5);
        pq.add(2);
        pq.add(4);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

내림차순 우선순위로 설정