PriorityQueue에 대해 이해해보자

김성수·2023년 5월 20일
1

Java

목록 보기
1/18

PriorityQueue

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 응용

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'이 맨 위에 위치하고 제거

profile
깊이 있는 소프트웨어 개발자가 되고 싶습니다.

0개의 댓글