[JAVA] Priority Queue

우선 순위 큐는 가장 높은 우선 순위 요소의 효율적인 검색을 지원하는 자료구조이다. 요소에는 대기열에서 액세스하거나 제거하는 순서를 결정하는 우선 순위가 할당된다. 우선순위 대기열은 FIFO(First-In-First-Out) 동작을 나타내어 우선순위가 가장 높은 요소가 항상 대기열의 맨 앞에 오도록 한다.

 

Priority Queue의 특징

1. 높은 우선순위의 요소를 하나씩 꺼내서 처리하는 구조

2. 보통 바이너리 힙으로 Priority Queue를 구현하고, 이는 이진트리 구조로 이루어져 있다.

3. 삽입, 삭제에 대해 시간 복잡도가 O(NLogN)이다.

 

Java Priority Queue 구현

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Create a priority queue
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add elements to the priority queue
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(2);
        pq.offer(4);

        // Retrieve and remove the highest-priority element
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

 

Class에 대한 Prioriry Queue

기본형에 대한 Priority Queue는 기본 타입에 대해 비교가 가능하여 우선순위를 정할 수 있지만, class를 직접 만들어 사용하는 경우 Comparable Interface를 implements하고, compareTo method를 우선 순위에 맞게 override하여 구현해 주면 된다.