[Java]우선순위큐(PriorityQueue)

우선순위큐(PriorityQueue)

• 스택은 후입선출, 큐는 선입선출을 특징을 가졌다. 이와 달리 우선순위큐는 사용자가 지정한 우선순위에 의거하여 원소를 꺼내는 특징이 있다.

기본적인 사용

• Java에서는 PrioryQueue 클래스를 이미 내부적으로 포함하고 있다. 이는 기본적으로 오름차순으로 수를 꺼낼 수 있도록 구현되어 있다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(3);
pq.offer(9);
pq.offer(1);

while(!pq.isEmpty()) {
	System.out.println(pq.poll());
}

정렬기준 정하기(사용자 정의)

• PriorityQueue의 생성하는 단계에서 Comparator 인터페이스를 재정의한다면 원소가 뽑히는 순서(정렬 기준)를 사용자가 원하는대로 재정의할 수 있다.

PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		return Integer.compare(o2, o1); // 내림차순 정렬
	}
});
pq.offer(5);
pq.offer(3);
pq.offer(9);
pq.offer(1);

while(!pq.isEmpty()) {
	System.out.println(pq.poll());
}

• 다음과 같이 Comparator 인터페이스를 생성하면 compare 함수를 재정의하여 원하는 비교 기준을 설정해주어야 한다. 위의 예시에서는 내림차순으로 정렬할 수 있도록 설정하였다.

객체 정렬

• 위와 같이 내부적으로 정렬 기준을 정하는 것은 다른 객체를 정렬하는 기준을 만들어줄수도 있다. 때문에 2차원 배열과 같은 내용도 정렬이 가능하다.

PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		// 만일 2차원 배열의 첫 번째 원소가 같다면, 2번째 원소를 기준으로 내림차순 정렬한다.
		if(o1[0] == o2[0]) {
			return Integer.compare(o2[1], o1[1]);
		}
		// 2차원 배열의 첫 번째 원소를 기준으로 오름차순 정렬한다.
		return Integer.compare(o1[0], o2[0]);
	}
});
pq.offer(new int[] {5, 2});
pq.offer(new int[] {3, 3});
pq.offer(new int[] {1, 4});
pq.offer(new int[] {1, 5});
pq.offer(new int[] {7, 5});

while(!pq.isEmpty()) {
	System.out.println(Arrays.toString(pq.poll()));
}

• 당연히 객체를 만들고, 객체의 원소를 비교 대상으로 두어 객체의 정렬 기준을 정해주는 것도 가능하다.
  • 객체 자체의 정렬 기준을 만들고 싶은 경우에는 정의한 객체에 Comparable 인터페이스를 포함시켜 객체 자체의 정렬 기준을 미리 정해주는 방법도 존재한다.

•  

•