우선순위 큐(Priority Queue)

• 우선순위가 높은 데이터가 먼저 나옴(!= FIFO)
  - 모든 데이터에 우선순위가 있음
  • Dequeue시 우선순위가 높은 순으로 나온다.
  • 우선 순위가 같은 경우 FIFO

앞쪽은 자연 순서에 따라 가장 적은 요소를 가지며 뒤쪽은 대기열에서 가장 큰 요소를 가리킵니다.
알파벳순 우선 순위 큐의 경우 ASCII 값이 고려되며 큐 요소는 ASCII 값에 따라 정렬됩니다.

특징

• PriorityQueue는 언바운드 큐입니다.
• PriorityQueue는 null 값을 허용하지 않습니다.
• 비교할 수 없는 객체의 경우 우선 순위 대기열을 만들 수 없습니다.
• PriorityQueue는 AbstractQueue, AbstractCollection, Collection 및 Object와 같은 클래스에서 상속됩니다.
• 큐의 헤드 또는 프론트에는 자연스러운 순서에 따라 최소 요소가 포함됩니다.
• 우선순위 큐 구현은 스레드로부터 안전하지 않습니다. 따라서 동기화된 액세스를 원하면 PriorityBlockingQueue를 사용해야 합니다.

PriorityQueue 클래스의 클래스 계층 구조

시간복잡도

삽입(enqueue) 및 삭제(dequeue) : O(log N)

PriorityQueue 클래스 사용법

PriorityQueue 요소는 자연스럽게 정렬됩니다. 순서를 변경하려면 비교자를 지정하고 PriorityQueue 객체를 생성하는 동안 사용해야 합니다. 그런 다음 PriorityQueue는 이 비교자를 사용하여 요소를 정렬합니다.

Java의 최소 우선 순위 대기열

• 우선 순위 대기열의 자연 순서는 대기열의 맨 위에 최소 또는 가장 작은 요소가 있으므로 순서가 오름차순이다.

	PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        //add element to the PriorityQueue
        pq.add(8);  
        pq.add(6);  
        pq.add(4); 
        pq.add(2);  
        pq.add(12);  
        pq.add(10);
        Integer val = null;
        while( (val = pq.poll()) != null) {
            System.out.print(val + " ");

2 4 6 8 10 12

Java의 최대 우선 순위 대기열

• 최대 우선순위 큐에는 내림차순이다. 즉, 최대 우선순위 큐의 헤드는 큐에서 가장 큰 요소를 반환.

//사용자지정비교자
	PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer lhs, Integer rhs) {
                if (lhs < rhs) return +1;
                if (lhs.equals(rhs)) return 0;
                    return -1;
            }
        });
        //add element to the PriorityQueue
        pq.add(8);  
        pq.add(6);  
        pq.add(4); 
        pq.add(2);  
        pq.add(12);  
        pq.add(10);
        Integer val = null;
        while( (val = pq.poll()) != null) {
            System.out.print(val + " ");

12 10 8 6 4 2

Comparator.reverseOrder()를 사용하면 간단하게 내림차순으로 된다.

Queue<Integer> pQ = new PriorityQueue<>(Comparator.reverseOrder());//내림차순

참고링크