Java Priority Queue 사용하기 - Comparable interface

우선순위 큐(Priority Queue)란, 선입선출 구조가 아닌, 우선순위가 가장 높은 데이터가 먼저 나오게 됩니다.

 

Java에서 우선순위 큐를 이용하는 방법을 예제와 함께 알아봅시다.

제가 PriorityQueue를 사용한 이유는 다익스트라 알고리즘에서 거리 정보중 최단 거리를 갖고 있는 위치 정보를 가져와야 하기 때문이죠.

그렇다면 위치정보와 동시에 거리정보를 가지고 있는 새 객체를 만들고, 이 객체를 PriorityQueue의 <E>에 할당하면 됩니다.

1. 우선순위 큐 선언

static PriorityQueue<Point> prq;
prq = new PriorityQueue<>();

 

2. 위치정보와 거리정보를 지닌 Point 객체 생성
 

class Point implements Comparable<Point> {
    int i, j;
    int dist = 9999;

    Point(int i, int j){
        this.i=i;
        this.j=j;
    }

    @Override
    public int compareTo(Point targetP) {
        return this.dist <= targetP.dist ? -1: 1;
    }
}

@Override는 Point안의 dist로 우선순위 큐를 구현하기 위한 오버라이딩 작업

 

3. @Override compareTo()

3-1. Comparable(=Interface) 구현 

Comparable의 compareTo()를 오버라이딩 하여 구현합니다. dist값을 기준으로 반환 값이 음수, 양수 인지에 따라 우선순위가 결정됩니다. 위의 this.dist<=targetP.dist ? -1: 1; 은 dist 정보가 적은 순을 구현한 것입니다.

 

compareTo() 메서드 원리

- 현재 객체 < 파라미터로 넘어온 객체: 음수 리턴

- 현재 객체 == 파라미터로 넘어온 객체: 0 리턴

- 현재 객체 > 파라미터로 넘어온 객체: 양수 리턴

- 음수 또는 0이면 객체의 자리가 유지되며, 양수인 경우에는 두 객체의 자리가 바뀌는 것입니다.

=> 즉, 작거나 0이면 객체의 자리가 유지되기 때문에 오름차순으로 구현이 되는 것입니다.