PriorityQueue는 두가지 정렬 방식이 존재한다.
기본적으로 오름차순이고, 내림차순으로 설정할 수도 있다.
오름차순으로 설정할 때는 아래와 같이 초기화하면 된다.
PriorityQueue<E> pQ = new PriorityQueue<>();
내림차순으로 설정할 때는
아래와 같이 소괄호 안에 Collections.reverseOrder()을 추가한다.
PriorityQueue<E> pQ = new PriorityQueue<>(Collections.reversOrder());
정수형, 실수형, 문자열, 객체 모두 정렬을 적용 가능하다.
실수형을 정렬하고 싶을 때는 아래와 같이 초기화하여 사용하면 된다.
PriorityQueue<Double> pQ = new PriorityQueue<>();
pQ.offer(2.5);
pQ.offer(1.5);
pQ.offer(1.0);
pQ.offer(2.0);
while(!pQ.isEmpty()){
System.out.println(pQ.poll());
}
// 출력
1.0
1.5
2.0
2.5
PriorityQueue는 요소를 추가하거나, 삭제할 때마다 우선순위에 맞는 정렬 순서로 재 배치한다.
이러한 방식 때문에 Queue보다 시간복잡도 차원에서 비효율적이다.
Queue는 입력과 삭제가 단방향으로 흐르기 때문에 시간복잡도가 O(1)이고,
PriorityQueue는 위에 설명한대로 재배치하는 성질 때문에 시간복잡도가 O(log n)이다.
따라서, 일반적으로 Queue가 PriorityQueue보다 효율적이라고 볼 수 있다.
하지만, PriorityQueue는 우선순위를 설정하여 정렬할 수 있다는 장점이 있다.
따라서, 우선순위에 따라 정렬을 재배치해야 하는 경우라면 PriorityQueue가 더 효율적일 수 있다.
Queue와 PriorityQueue의 차이를 간략하게 설명해보겠다.
도착시간 s와 나가는 시간 e가 주어진다.
나가는 시간 e 보다 도착시간이 늦거나 같다면 서로 같이 존재할 수 없다.
반면에 나가는 시간 e보다 도착시간이 작다면 서로 함께 존재할 수 있다.
이 때, 한 공간에 최대로 존재할 수 있는 인원의 수를 구해야할 때
Queue로 문제를 접근하면 이 문제를 해결할 수 없다.
간단한 예시를 들자면 Queue로 문제를 풀이했을 때
0 1
0 2
0 3
0 3
..
0 76
1 2
1 2
1 3
..
1 76
2 3
2 4
..
2 76
..
75 76
76 77
위와 같이 도착 시간과 나가는 시간이 주어졌을 때
현재 도착 시간 s = 76으로 주어졌기 때문에
0 76
1 76
2 76
3 76
..
75 76
위와 같은 조건 즉, e = 76인 조건은 모두 해당 공간에서 나가야 한다.
하지만 Queue는 딱 '0 76' 이 하나만의 인덱스 밖에 제거할 수가 없다.
왜냐하면 요소들이 들어온 순서대로 정렬되어 있고 요소를 제거하는 방식이
FIFO 방식이기 때문에 0 76 이후의 '1 76', '2 76', .. '75 76'의 요소들은
제거할 수 없기 때문이다.
하지만, PriorityQueue는 요소를 추가하거나 삭제할 때마다 조건에 맞도록
최솟값을 맨 위로 정렬해준다.
따라서, 위와 동일한 조건이 주어졌고 s = 76인 상황일 때
e 값이 76보다 작거나 같은 모든 값들을 제거할 수 있게 된다.
'0 76' 제거 후 재 정렬하여
'1 76' 이 맨 위에 위치하고 제거되면
'2 76'이 맨 위에 위치하고 제거되면
..
'75 76'이 맨 위에 위치하고 제거