1. 우선순위 큐 (Priority Queue) 란
우선순위 큐란 임의의 데이터 항목이 삽입되고, 일정한 순서에 의해 삭제되는 데이터 구조이다. 즉, 들어간 데이터의 순서에 상관없이 우선순위가 높은 데이터가 먼저 삭제되는 데이터 구조이다.
힙(heap)은 내부 노드에 키를 저장하면서 힙순서, 완전 이진트리의 두 속성을 만족하는 이진트리이다.
- 힙 순서 : 모든 부모-자식 관계에서 부모노드의 키가 자식노드의 키보다 작거나 같도록 구성된 이진트리.
- 완전이진트리 : 힙의 높이를 h라 할 때, i = 0, 1, 2, ..., h-1에 대해 깊이가 i인 노드가 2**i개 존재하고, 깊이 h-1에서 내부 노드들은 외부노드들의 왼쪽에 존재한다. 부모노드들은 항상 2개의 자식노드를 가지고 있다.
우선순위 큐는 힙으로 구현될 수 있다.
2. Java에서의 Priority Queue 사용
java는 PriorityQueue라는 자료형을 제공한다. 이를 통하여 우선순위 큐를 쉽게 구현할 수 있다.
기본적으로 우선순위 큐를 선언하면, 값이 작은 것을 우선순위로 하는 자료구조가 생성된다.
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// 데이터 형식을 integer로 하는 우선순위 큐 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 데이터 삽입
priorityQueue.add(1);
priorityQueue.add(4);
priorityQueue.add(3);
// 데이터 삭제
System.out.println(priorityQueue.poll());
// 데이터 접근
System.out.println(priorityQueue.peek());
}
}
위의 코드를 실행하면, 처음엔 가장 우선순위가 높은 1이 삭제되고 출력되어 두번째엔 그 다음으로 우선순위가 높은 3이 출력되는 것을 볼 수 있다.
3. PriorityQueue custom
항상 우선순위가 최소값이 아닐 수가 있다. 이럴 경우, 직접 코드를 수정하여 우선순위를 설정할 수 있다.
다음은 백준 11286번 문제를 3가지 방법으로 해결한 것이다.
1) Comparable
import java.util.PriorityQueue;
import java.util.Scanner;
class Data implements Comparable<Data> {
int abs;
int num;
public Data(int abs, int num) {
this.abs = abs;
this.num = num;
}
@Override
public int compareTo(Data x) {
// 절대값이 작은 경우, 더 높은 우선순위를 갖는다.
if (this.abs < x.abs) return -1;
// 절대값이 같은 경우, 숫자의 값이 작으면 더 높은 우선순위를 갖는다.
else if (this.abs == x.abs && this.num < x.num) return -1;
else return 1;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 숫자 입력
int n = scanner.nextInt();
PriorityQueue<Data> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
int input = scanner.nextInt();
if (input == 0) {
if (priorityQueue.size() == 0) {
System.out.println(0);
}
else {
System.out.println(priorityQueue.poll().num);
}
}
else {
Data data = new Data(getAbs(input), input);
priorityQueue.add(data);
}
}
}
public static int getAbs(int n) {
if (n < 0) return n * -1;
else return n;
}
}
만약 PriorityQueue에 새로운 class를 정의하여 해당 class를 자료형으로 하는 우선순위 큐를 생성할 때,
comparable을 상속 받아 class를 정의하고 compareTo() 함수를 override하여 우선순위를 정의할 수 있다.
2) Comparator
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
class Data {
int abs;
int num;
public Data(int abs, int num) {
this.abs = abs;
this.num = num;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
// comparator 선언
Comparator<Data> comparator = new Comparator<>() {
@Override
public int compare(Data o1, Data o2) {
if (o1.abs < o2.abs) return -1;
else if (o1.abs == o2.abs && o1.num < o2.num) return -1;
else return 1;
}
};
// comparator를 이용하여 우선순위 설정
PriorityQueue<Data> priorityQueue = new PriorityQueue<>(comparator);
for (int i = 0; i < n; i++) {
int input = scanner.nextInt();
if (input == 0) {
if (priorityQueue.size() == 0) {
System.out.println(0);
}
else {
System.out.println(priorityQueue.poll().num);
}
}
else {
Data data = new Data(getAbs(input), input);
priorityQueue.add(data);
}
}
}
public static int getAbs(int n) {
if (n < 0) return n * -1;
else return n;
}
}
새로운 class를 정의하고 Comparator을 정의하여 우선순위를 정의할 수 있다.
3) 람다식
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 숫자 입력
int n = scanner.nextInt();
// 우선순위 큐 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> {
// 절대값이 같은 경우, 값이 작으면 더 높은 우선순위
if (getAbs(o1) == getAbs(o2)) return o1 > o2 ? 1 : -1;
// 절대값이 작은 경우 더 높은 우선순위
return getAbs(o1) > getAbs(o2) ? 1 : -1;
});
for (int i = 0; i < n; i++) {
int input = scanner.nextInt();
if (input == 0) {
if (priorityQueue.size() == 0) {
System.out.println(0);
}
else {
System.out.println(priorityQueue.poll());
}
}
else {
priorityQueue.add(input);
}
}
}
public static int getAbs(int n) {
if (n < 0) return n * -1;
else return n;
}
}
위의 코드는 우선순위 큐를 선언할 때, 람다식을 이용하여 우선순위를 정하는 코드이다.
* 기억할 점!
java에서 PriorityQueue는 내부적으로 최소 힙 구조를 사용하여 동작한다.
따라서 o1, o2 두 데이터에 대한 Comparator에서
양수 값 반환 -> o1이 o2 보다 우선순위가 낮다. o2가 더 앞에 위치해야 한다.
음수 값 반환 -> o1이 o2 보다 우선순위가 높다. o1이 더 앞에 위치해야한다.
결국, o1에 대한 우선순위를 생각할 때,
우선순위가 높을 경우 음수를 반환하고, 우선순위가 낮은 경우 양수를 반환하면 된다.
<참고 자료>
- 전공 서적
[Java] Priority Queue 매개변수에 람다식 쓰는 이유가 뭐야?
Priority Queue 는 무엇일까...
velog.io
- https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
PriorityQueue (Java Platform SE 8 )
An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does
docs.oracle.com
- https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html
Comparator (Java SE 11 & JDK 11 )
Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and
docs.oracle.com
'개발 언어 > JAVA' 카테고리의 다른 글
| [JAVA/알고리즘] HashSet clear()와 removeAll() 메모리 (백준 1697) (0) | 2025.03.05 |
|---|---|
| [JAVA/알고리즘] 분할 정복 알고리즘 Divide and conquer (백준 2630) (0) | 2025.03.03 |
| [JAVA/알고리즘] 동적 계획법 Dynamic Programming (백준 1463) (0) | 2025.03.01 |
| [JAVA/알고리즘] 집합 HashSet (백준 11723) (0) | 2025.02.27 |
| [JAVA/알고리즘] 매개 변수 탐색 (백준 1654) (0) | 2025.02.26 |