# 우선순위 큐 (Priority Queue)
정의
우선순위 큐는 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료구조입니다.
- 모든 항목에는 우선순위가 있습니다.
- 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다.
- 두 요소의 우선 순위가 같은면 queue의 순서에 따라 제공됩니다.
- 우선순위 큐는 힙을 기반으로 구현됩니다.
- 시뮬레이션 시스템, 네트워크 트래픽 제어, OS에서 작업의 스케쥴링 등에 사용됩니다.
# 데이터 삽입&삭제 시간복잡도
- 배열, 연결 리스트, 힙으로 구현 가능하지만 힙을 이용하는 것이 가장 효율적입니다.
- 힙을 이용한 구현이 이루어지기에
O(logN)
입니다.
# 자바에서의 우선순위 큐
- 일반적인 큐를 사용하는 것처럼
add()
,peek()
,poll()
등의 메소드를 사용할 수 있습니다. PriorityQueue
는 동기화 되어있지 않기 때문에 동기화가 필요하다면,PriorityBlockingQueue
를 사용해야 합니다.
import java.util.PriorityQueue;
public class Sample {
public static void main(String[] args) {
// 우선순위 큐 생성
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 우선순위 큐에 값 삽입
pq.add(4);
pq.offer(1);
// 우선순위 큐에서 값을 꺼내기
pq.poll(); // 1이 출력된다.
}
}
- add() 대신 offer() 메소드를 사용해도 동일한 결과가 산출됩니다.
- 이외의 로직들은 Queue의 기본적인 기능과 유사하기에 생략하도록 하겠습니다.
# 우선순위 큐의 우선순위를 지정하기
- 위의 예제는 정렬이 쉽게 가능한 정수 자료형이었기에, 따로 우선순위를 지정하지 않았습니다.
- 만약에 순서를 직접 정의하여 정렬을 하고 싶다면 어떨까요?
class Student implements Comparable<Student> {
int age;
int classNumber;
@Override
public int compareTo(Student o) {
return this.age - o.age;
}
}
- 위처럼 Comparable 인터페이스를 이용하여 객체 자체에 대한 비교 방법을 미리 구현해두면, 기본 생성자로 생성시 원하는 순서대로 정렬됩니다.
- 우선순위 큐에서 제공하는 생성자 중에, 우선순위를
Comparator
클래스로 받는 생성자가 존재합니다. - 따라서
Comprator
를 생성할 때 넘겨줌으로써 정렬 순서를 지정해주는 방법이 있습니다.
// Collections에서 제공하는 Comparator
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
// 직접 구현하는 Comparator
PriorityQueue<Student> pq = new PriorityQueue<>(new Comparator<Student>() {
@Override
public int compare(Student p1, Student p2) {
return p1.age >= p2.age ? 1 : -1;
}
});
# 참고자료
← 덱 (Deque) 그래프(Graph) →