[JAVA] Priority Queue(우선순위 큐) 우선순위 조건 변경하기

 

Priority Queue

FIFO(First In First Out)인 일반적인 Queue와 다르게 Priority Queue는 우선순위가 높은 데이터가 먼저 Out된다.
기본적으로 오름차순 정렬을 하게 되는데 정렬 기준을 바꾸고 싶다면 람다식을 이용하거나 Comparator, Comparable를 이용해야 한다.

 

• Integer는 Collections.reverseOrder()를 통해 간단하게 내림차순 정렬을 할 수 있다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(5);
pq.add(7);
pq.add(10);
pq.add(3);

System.out.println(pq.poll()); // 10 출력

add가 아닌 offer를 사용해도 됨..!

 

응용을 해보자!

좌표가 저장되어 있는 이차원 배열이 있고, 원점에서 부터 거리가 가까운 순서대로 출력하고자 한다면 아래와 같이 작성하면 된다.

• 오름차순

int[][] points = {{1,3}, {-2,2}, {-4,1}};

//1. 람다식 이용
Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]*a[0]+a[1]*a[1])-(b[0]*b[0]+b[1]*b[1]));

//2. Comparator 이용
Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		int o1Result = o1[0]*o1[0] + o1[1]*o1[1];
		int o2Result = o2[0]*o2[0] + o2[1]*o2[1];
		return o1Result-o2Result;
	}
});

//queue에 add하는 부분 생략

int size = pq.size();

for(int i = 0; i<size; i++){
	int[] data = pq.poll();
	System.out.println(data[0]+","+data[1]+" : "+(data[0]*data[0]+data[1]*data[1]) );
}

/* 결과
	-2,2 : 8
	1,3 : 10
	-4,1 : 17
*/

 

• 내림차순

반대로 원점에서 부터 거리가 먼 순서대로 출력하고자 한다면 아래와 같이 작성하면 된다.

//1. 람다식 이용
Queue<int[]> pq = new PriorityQueue<>((a,b)->(b[0]*b[0]+b[1]*b[1])-(a[0]*a[0]+a[1]*a[1]));

//2. Comparator 이용
Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		int o1Result = o1[0]*o1[0] + o1[1]*o1[1];
		int o2Result = o2[0]*o2[0] + o2[1]*o2[1];
		return o2Result-o1Result;
	}
});

//queue에 add하는 부분 생략

int size = pq.size();

for(int i = 0; i<size; i++){
	int[] data = pq.poll();
	System.out.println(data[0]+","+data[1]+" : "+(data[0]*data[0]+data[1]*data[1]) );
}


/* 결과
	-4,1 : 17
	1,3 : 10
	-2,2 : 8
*/