우선순위 큐

우선순위 큐?

Priority Queue?
 큐와 동일하게 FIFO 구조를 가지는데, 특이한점은 들어온 순서가 아닌 우선순위에 따라서 삽입/삭제 순서가 정해진다

• 따로 정렬 기준을 정하지 않을경우, 오름차순으로 정렬이된다 (작은수가 우선순위)
• reverseOrder()를 사용하면 내림차순으로 정렬이된다 (큰 수가 우선순위)

 

우선순위 큐 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리
2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어짐
3. 힙으로 구성되어있어 시간복잡도는 O(NlogN)이다
4. 우선순위를 중요시할때 사용한다

 

우선순위큐 메서드

선언)
PriorityQueue<객체타입> [우선순위큐 이름] = new PriortyQueue<>();

• 삽입
  • add() / offer()을 사용하여 삽입
    • add()는 가득차있으면, Exception 예외
    • offer()는 가득차있으면 ,false 반환

priorityQueue.add(1);
priorityQueue.offer(2);

• 삭제
  • remove() / poll()을 이용하여 삭제
    • remove()는 없으면 Exception 발생
    • poll()은 없으면 null 반환

priortyQueue.remove();
priortyQueue.poll();

• 조회
  • peek() / element()을 이용하여 조회
    • peek()은 비어있다면 null 반환
    • element()은 비어있다면 Exception 발생

priortyQueue.peek();
priortyQueue.element();

 

우선순위 큐 정렬기준

• 오름차순

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

• 내림차순

PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

• 커스텀
  • 람다식으로 표현방법 (1)
  • 클래스로 구현방법(2)

//람다식 (1)
PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> {
            if(o1 < o2){
                return 1;
            }else if(o1==o2){
                return 0;
            }else{
                return -1;
            }
        });
        
        
        
        
        
        
        
//클래스로 구현 (2)
public class QueuePrioritySort implements Comparator<Integer>{
        
        /**
         * 1 : o1이 더 우선순위
         * -1 : o2이 더 우선순위
         * 0 : 같음 => 이걸 커스텀해서 처리해준것
         */
        @Override
        public int compare(Integer o1, Integer o2){
            int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);

            if(first_abs == second_abs){
                return o1>o2 ? 1 : -1;
            }else{
                return first_abs - second_abs;
            }
        }
}

public class App {
    public static void main(String[] args) throws Exception {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new QueuePrioritySort());
        
        //...
}