Priority Queue란
Priority Queue란 우선순위 큐 로써 일반적인 큐의 구조(FIFO)를 가지면서, 데이터가 들어온 순서대로 나가는 것이 아닌 우선순위를 먼저 결정하고 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
Priority Queue를 사용하기 위해서는 우선순위 큐에 저장할 객체는 필수적으로 comparable Interface를 구현해야 한다.
Comparable Interface를 구현하려면 compareTo 메서드를 override 하게되고 객체에서 처리할 우선순위 조건을 return 해주면 Priority Queue가 알아서 우선순위가 높은 객체를 추출해준다.
PriorityQueue는 heap으로 구현하는 것이 일반적이다.
데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다.
Priority Queue의 특징
- 높은 우선순위의 요소를 먼저 꺼내 처리하는 구조이다.
- 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
- 내부 구조가 힙으로 구성되어 있기에 시간복잡도는 O(NlogN)이다.
- 우선순위를 중요시 해야하는 상황에서 주로 쓰인다.
Priority Queue 선언
// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자) PriorityQueue<Integer> pq = new PriorityQueue<>(); // 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자) PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());```
기본 메소드
add() : 우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생 offer() : 우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환 poll() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 null 반환 remove() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생 isEmpty() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생 clear() : 우선순위 큐를 초기화 size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환
Priority Queue 기본 사용법
import java.util.PriorityQueue;
public class Example {
public static void main(String[] args) {
// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();
pQ.offer(1); // pQ에 원소 1 추가
pQ.offer(3); // pQ에 원소 3 추가
pQ.offer(5); // pQ에 원소 4 추가
pQ.offer(2); // pQ에 원소 2 추가
pQ.offer(4); // pQ에 원소 4 추가
// pQ가 비어있면: true, 그렇지 않으면 : false
while(!pQ.isEmpty()) {
// pQ에 첫 번째 값을 반환하고 제거, 비어있다면 null 반환
System.out.println("pQ.poll() = " + pQ.poll());
}
}
}Priority Queue 클래스 객체 우선순위 정하기
import java.util.PriorityQueue;
public class Example {
private class Student {
int mathScore; // 수학점수
int engScore; // 영어점수
Student(int mathScore, int engScore){
this.mathScore = mathScore;
this.engScore = engScore;
}
}
public st
atic void main(String[] args) {
PriorityQueue<Student> pQ = new PriorityQueue<>();
}
}다음과 같이 Student 클래스의 객체를 우선순위 큐에 넣으려 한다. 예를들어 수학점수가 낮은 학생이 우선순위가 높다. 그리고 수학점수가 같을 경우 영어점수가 높은 학생이 우선순위가 높다고 했을 때의 이를 정의하는 코드는 다음과 같다.
import java.util.Comparator;
import java.util.PriorityQueue;
class Student {
int mathScore; // 수학점수
int engScore; // 영어점수
public Student(int mathScore, int engScore){
this.mathScore = mathScore;
this.engScore = engScore;
}
}
// 클래스 객체의 우선순위를 위한 클래스
class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
if (o1.mathScore == o2.mathScore) {
return o2.engScore - o1.engScore;
} else {
return o1.mathScore - o2.mathScore;
}
}
}
public class Example {
public static void main(String[] args) {
// 클래스 객체에 대한 우선순위 기준 제공
PriorityQueue<Student> pQ = new PriorityQueue<>(1, new StudentComparator());
pQ.offer(new Student(70, 50)); // 우선순위 큐에 클래스 객체를 추가
pQ.offer(new Student(60, 50)); // 우선순위 큐에 클래스 객체를 추가
pQ.offer(new Student(70, 40)); // 우선순위 큐에 클래스 객체를 추가
while (!pQ.isEmpty()) {
Student s = pQ.poll();
System.out.printf("Student\'s MathScore and engScore: %d, %d \n", s.mathScore, s.engScore);
}
}
} 
참고 :
https://kbj96.tistory.com/49
https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90
