PriorityQueue, Comparator

자바의 PriorityQueue(우선순위 큐)는 높은 우선순위의 요소를 먼저 꺼내서 처리하는 자료구조이다. 내부 구조는 힙으로 구성되어 있어 이진 트리 구조이고, 시간복잡도는 O(NlogN)이 소요된다. 

PriorityQueue의 자세한 내용은 https://st-lab.tistory.com/219 을 참고하면 잘 학습할 수 있다.

https://st-lab.tistory.com/219

 

✔️ 우선순위 부여하기

PriorityQueue<Integer> pq = new PriorityQueue();

PriorityQueue는 기본적으로 오름차순으로 구성되기 때문에, 위처럼 Integer로 비교할 때는 문제없이 오름차순으로 구성한다. 

 

class Member {
    int age;
    int height;
    int weight;

    // 전체 생성자
}

PriotrityQueue<Member> pq = new PriotrityQueue();

하지만, 위와 같이 비교해야 하는 기준이 모호할 때는 PriorityQueue가 어떻게 구성될까?

"Exception in thread "main" java.lang.ClassCastException: class Main$Member cannot be cast to class java.lang.Comparable (Main$Member is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')" 

런타임 중 "ClassCastException"이 발생한다. Member 객체를 Comparable 타입으로 캐스팅하려고 했지만, 실제로는 Member가 Comparable을 구현하지 않아서 발생한 문제이다. 

 

Comparable (자기 자신과 매개변수를 비교)

• int compareTo(T other) 
  • 음수 : 앞(자기 자신)이 더 작다
  • 양수 : 앞(자기 자신)이 더 크다
  • 0 : 두 개의 원소가 동일

public class ClassName implements Comparable<Type> {
    
    //code
    
    @Override
    public int compareTo(Type o) {
        // 비교 구현
    }
}

 

Comparator (두 매개변수를 비교)

• int compare(T o1, T o2)
  • 음수 : 앞이 더 작다는 의미
  • 양수 : 앞이 더 크다는 의미

import java.util.Comparator;
import java.util.PriorityQueue;

// 클래스에서 사용할 때
public class ClassName implements Comparator<Type> {
    @Override
    public int compare(Type o1, Type o2) {
        return o1 - o2;
    }
}

// Priority Queue에서 사용할 때
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
});

 

✔️ PriorityQueue, Comparator

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
}

PriorityQueue<Member> pq = new PriorityQueue<>(new Comparator<Member>() {
    @Override
    public int compare(Member m1, Member m2) {
        return m1.age - m2.age; 
    }
});

// 람다식 적용
PriotrityQueue<Member> pq = new PriotrityQueue((m1, m2) -> m1.age - m2.age);

Comparator는 함수형 인터페이스이기 때문에, PriorityQueue에서 다음과 같이 람다식을 사용하여 정렬 기준을 작성할 수 있다. 

 

위에서 PriorityQueue는 기본적으로 오름차순을 기준으로 삼는다고 이야기 했다. 이 말은 선행 원소가 후행 원소보다 "작다"는 뜻이다. 즉, compareTo, compare를 사용하여 객체를 비교할 때 음수가 나오면 두 원소의 위치를 바꾸지 않는다는 말이다. 왜냐하면 선행 원소가 후행 원소보다 작기 때문이다.

 

예를 들어 {1, 3, 2}를  compareTo, compare를 사용하여 비교한다고 해보자. 

 

index1 원소와 index2 원소를 비교하면 1 - 3 = -2(음수) 이므로 선행 원소(1)이 후행 원소(3)보다 작다고 판단하여 순서를 바꾸지 않는다.

index2 원소와 index3 원소를 비교하면 3 - 2 = 1(양수) 이므로 선행 원소(3)이 후행 원소(2)보다 크다고 판단하여 순서를 바꾼다. 

 

이를 통해 다음과 같이 일반화를 할 수 있다. 

• 결과가 음수일 경우 : 두 원소의 위치를 바꾸지 않는다. 
• 결과가 양수일 경우 : 두 원소의 위치를 바꾼다. 

 

// 1. age를 기준으로 오름차순
PriotrityQueue<Member> pq = new PriotrityQueue((m1, m2) -> m1.age - m2.age);

// 2. age를 기준으로 내림차순
PriotrityQueue<Member> pq = new PriotrityQueue((m1, m2) -> m2.age - m1.age);

Member의 age 원소는 다음과 같이 제공된다고 가정하자 {1, 3, 2}

1. (m1, m2) -> m1.age - m2.age

• 1 - 3 = -2, 결과가 음수이므로 m1이 더 작다고 판단하여 순서를 유지한다. 
  • 결과 : {1, 3, 2}
• 3 - 2 = 1, 결과가 양수이므로 m1이 더 크다고 판단하여 순서를 바꾼다. 
  • 결과 : {1, 2, 3}

2. (m1, m2) -> m2.age - m1.age

• 3 - 1 = 2, 결과가 양수이므로 m1이 더 크다고 판단하여 순서를 바꾼다. 
  • 결과 : {3, 1, 2}
• 2 - 1 = 1, 결과가 양수이므로 m1이 더 크다고 판단하여 순서를 바꾼다. 
  • 결과 : {3, 2, 1}

 

참고

https://st-lab.tistory.com/243