[Java] 우선순위 큐(Priority Queue)

최단 경로 알고리즘에서 다익스트라 알고리즘을 공부하는데 '우선 순위 큐'를 이용하면 시간 복잡도를 획기적으로 줄일 수 있다는 방법을 알게되었다. 그래서 우선순위 큐의 간단한 사용법을 알아보고자 한다.

PriorityQueue

 도로에서 차량의 우선순위를 생각해보면, 보통 먼저 진입하는 차가 먼저 가게 되지만, 구급차 혹은 소방차가 나타나면 모든 차들은 긴급한 차량을 위해 도로를 양보한다. 이런 긴급 차량들은 도로 교통법에 의해 우선 순위를 갖는다. 컴퓨터에서도 우선순위의 개념이 필요할 때가 있다. 예를 들어 네트워크 패킷 중에서도 네트워크 관리와 관련된 패킷은 다른 일반 패킷보다 우선 순위를 갖는다.

 

 우선순위 큐는 이러한 우선 순위의 개념을 큐에 도입한 자료구조이다. 보통 큐는 선입선출(First-In First-Out, FIFO)원칙에 의해 먼저 들어온 데이터가 먼저 나간다. 그러나 우선순위 큐에서는 데이터들이 우선 순위를 갖고 우선 순위가 높은 데이터가 먼저 나가게 된다.

Stack	가장 최근에 들어온 데이터가 나감
Queue	가장 먼저 들어온 데이터가 나감
PriorityQueue	가장 우선 순위가 높은 데이터가 나감

 

우선순위 큐는 힙(Heap)을 이용하여 구현하는 것이 일반적이다. 데이터를 삽입할 때 우선 순위를 기준으로 최대 힙 또는 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가며 적절한 자리를 찾아서 옮기는 방식으로 진행된다.

PriorityQueue 특징

• 높은 우선 순위의 요소를 먼저 꺼내 처리하는 구조(Queue에 들어가는 원소는 비교 가능한 기준이 있어야 한다.)
• 내부 요소는 힙으로 구성되어 이진 트리 구조로 이루어짐
• 내부 구조가 힙으로 구성되어있기 때문에 시간 복잡도는 O(Nlog N)

우선 순위 변경하기

• 우선순위를 정하는 기준은 Java의 정렬 기준과 동일하다.
• Java는 기본적으로 낮은 숫자부터 큰 숫자까지 오름차순으로 정렬하게 되는데, 만약 다른 오름차순으로 정렬하고 싶다면 Comparator 클래스나 Comparable 인터페이스를 이용해야 한다.
• Ex) 객체의 어떤 값에 따라 우선순위를 정해 정렬해야 할때, 오름차순이 아닌 내림차순 정렬을 할때 등등
• Integer는 Collections.reverseOrder()를 사용해 내림차순 정렬을 할 수 있다.

PriorityQueue 사용

    public static void main(String[] args) {

        //PriorityQueue 오름차순 생성자
        Queue<Integer> priorityQ_asc = new PriorityQueue<>();
        
        //PriorityQueue 내림차순 생성자
        Queue<Integer> priorityQ = new PriorityQueue<>(Comparator.reverseOrder());
        
        //일반적인 Queue
        Queue<Integer> Q = new LinkedList<>();
        
        int[] arr = {10, -10, 15, 3};
    }
}

# 원소 추가 : add() / offer()

        priorityQ_asc.add(arr[0]);
        priorityQ_asc.add(arr[1]);
        priorityQ_asc.add(arr[2]);
        priorityQ_asc.add(arr[3]);

        priorityQ.add(arr[0]);
        priorityQ.add(arr[1]);
        priorityQ.add(arr[2]);
        priorityQ.add(arr[3]);

        Q.add(arr[0]);
        Q.add(arr[1]);
        Q.add(arr[2]);
        Q.add(arr[3]);
        
        System.out.println("\n# Queue");
        Q.stream().forEach(i -> System.out.print(i + " "));

        System.out.println("\n# Priority Queue DESC");
        priorityQ.stream().forEach(i -> System.out.print(i + " "));

        System.out.println("\n# Priority Queue ASC");
        priorityQ_asc.stream().forEach(i -> System.out.print(i + " "));        

# 원소 꺼내기

• poll() : 첫 번째 값을 반환하고 제거
• remove() : 첫 번째 값 제거
• clear() : 우선순위 큐 초기화
• peek() : 첫 번째 값을 반환하고 제거는 하지 않는다.

 

# References

woovictory님의 블로그

코딩팩토리님의 블로그