우선순위 큐 - Java에서 다루기

우선순위 큐(Priority Queue)

일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조 입니다. 대표적인 예로는 은행업무를 기다리는 손님들의 대기열 입니다. 이런 큐의 특성과 달린 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 됩니다. 대표적인 예로는 병원의 응급환자를 생각하면 됩니다. 은행과 달리 위급한 우선순위에 따라 먼저 처리되기 때문입니다.

우선순위 큐 사용하기

우선순위 큐도 Java내부적으로 구현이 되어 있습니다. 일반적인 큐를 사용하는 것처럼 add(); peek(); poll(); 등의 메소드를 사용할 수 있습니다.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

priorityQueue.add(4); //offer(); 메소드를 사용해도 동일하게 추가됩니다.
priorityQueue.add(3);
priorityQueue.add(2);
priorityQueue.add(1);

Integer poll = priorityQueue.
System.out.println(poll); //출력결과 1

일반적인 큐와 다르게 가장 먼저 들어간 4가 아니라, 우선순위가 높은 1이 들어갔습니다. 기본적으로 숫자는 낮은 것이 우선순위를 높게 봅니다.

우선순위 변경하기

우선순위를 정하는 기준은 Java의 정렬기준과 동일합니다. Java는 기본적으로 낮은 숫자부터 큰 숫자까지 오름차순으로 정렬하게 되는데, 만약 다른 오름차순으로 사용하고 싶다면 Compartor 클래스나 Comparable 인터페이스를 이용해야 합니다. 정렬기준으로 정하는 것과 동일합니다. Integer와 같은 숫자는 Collections.reversOrder()를 사용하면 간편하게 우선순위를 변경할 수 있습니다.

//우선순위를 높은 숫자위주로 변경
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

priorityQueue.add(1); //offer(); 메소드를 사용해도 동일하게 추가됩니다.
priorityQueue.add(2);
priorityQueue.add(3);
priorityQueue.add(4);

Integer poll = priorityQueue.
System.out.println(poll); //출력결과 4