JAVA - 우선순위 큐 (Priority Queue)

👀Priority Queue란?

일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

👀Priority Queue의 특징

• 사용자가 정의한 높은 우선순위의 Element를 먼저 꺼내는 구조이다.

• 내부는 힙의 구조(Binary-Tree)로 이루어져있다.

• 우선순위를 중요시하는 상황에 쓰인다!

• 이진트리의 높이는 최대 N, 최소 log2(n+1)이다.

  👀Priority Queue의 사용 방법

  Priority Queue의 선언
  우선순의 큐의 선언 type은 사용자가 정의한 class도 가능하다
  물론 Integer나 String도 가능함!

  PriorityQueue <Test> q = new PriorityQueue<>

  사용자 정의 class로 큐를 선언했을 경우, 클래스의 특정 필드를 기준으로 정렬할 수 있는데, 그 방법은 다음과 같다.
  

import java.util.*;

class Test implements Comparable<Test>{
    int value=0;
    Test(int v){
        value = v;
    }
    @Override //Comparable 인터페이스의 comapreTo메소드를 재정의하였다.
    public int compareTo(Test test){ //오름차순으로 정렬하는 방식.
        if(test.value < value){ 
            return 1;
        }
        else if(test.value >value){
            return -1;
        }
        return 0;
    }
}

class priorityQueue {
    public static void main(String[] args){
        PriorityQueue <Test> q = new PriorityQueue<>();
        q.add(new Test( 3));
        q.add(new Test( 2));
        q.add(new Test( 4));
        q.add(new Test( 6));
        q.add(new Test( 5));

        while(q.size()!=0){
            Test a = q.remove();
            System.out.println(a.value);
        }

    }
}

만약, class의 필드를 기준으로 내림차순으로 정렬하고 싶다면, 큐를 선언할 때

PriorityQueue <Test> queue = new PriorityQueue<>(Collections.reverseOrder())

처럼, 선언하면 내림차순으로 정렬 가능하다.

• 매우 자주 쓰이는 기능들이므로 꼭 숙달하자.