PrioryityQueue(우선순위 큐)

 

Priority Queue의 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야함) 2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음   3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)

4. 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰임

 

 Priority Queue 사용법 

Priority Queue 선언

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

자바에서 우선순위 큐 라이브러리를 사용하고 싶다면 java.util.PriorityQueue 를 import 하고 Queue<Element> queue = new Queue<>()와 같은 형식으로 선언하면 됩니다. 기본은 우선순위가 낮은 숫자가 부여되고 만약 높은 숫자가 우선순위가 되게 하고 싶다면 선언 시 Collections.reverseOrder() 메서드를 활용합니다.

 

Priority Queue 값 추가

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가

자바의 우선순위 큐에 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 됩니다. add(value) 메서드의 경우 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킵니다. 우선순위 큐에 값을 추가한다면 아래 그림과 같은 과정을 통해 즉시 정렬이 됩니다.

 

Priority Queue 값 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

우선순위 큐에서 값을 제거하고 싶다면 poll()이나 remove()라는 메서드를 사용하면 됩니다. 값을 제거할 시 우선순위가 가장 높은 값이 제거됩니다. poll() 함수는 우선순위 큐가 비어있으면 null을 반환합니다. pop을 하면 가장 앞쪽에 있는 원소의 값이 아래 그림과 같이 제거됩니다. queue의 모든 요소를 제거하려면 clear() 메서드를 사용합니다.

 

 

Priority Queue에서 우선순위가 가장 높은 값 출력

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//int형 priorityQueue 선언 priorityQueue.offer(2); // priorityQueue에 값 2 추가 priorityQueue.offer(1); // priorityQueue에 값 1 추가 priorityQueue.offer(3); // priorityQueue에 값 3 추가 priorityQueue.peek(); // priorityQueue에 첫번째 값 참조 = 1

Priority Queue에서 우선순위가 가장 높은 값을 참조하고 싶다면 peek()라는 메서드를 사용하면 됩니다. 위의 예시에서는 우선순위가 가장 높은 1이 출력됩니다.

 

 

 

 

Costom Class

 

class CustumClass implements Comparable<CustumClass> {

    private int writeRowNumber;
    private String content;

    public CustumClass(int writeRowNumber, String content) {
        this.writeRowNumber = writeRowNumber;
        this.content = content;
    }

    public int getWriteRowNumber() {
        return this.writeRowNumber;
    }

    public String getContent() {
        return this.content;
    }

    @Override
    public int compareTo(CustumClass cc) {

        if (this.writeRowNumber > cc.getWriteRowNumber())
            return 1;
        else if (this.writeRowNumber < cc.getWriteRowNumber())
            return -1;
        return 0;
    }
}

Priority Queue에 적용

    public static void main(String[] args) {

        PriorityQueue<CustumClass> priorityQueue = new PriorityQueue<>();

        priorityQueue.add(new CustumClass(3650, "10년후 글"));
        priorityQueue.add(new CustumClass(31, "한달 후 글"));
        priorityQueue.add(new CustumClass(1, "첫번째 글"));
        priorityQueue.add(new CustumClass(365, "1년후 글"));

        while (!priorityQueue.isEmpty()) {
            CustumClass cc = priorityQueue.poll();
            System.out.println("글 넘버 : " + cc.getWriteRowNumber() + " 글 내용 : " + cc.getContent());
        }
    }
    
 /* 실행 결과
글 넘버 : 1 글 내용 : 첫번째 글
글 넘버 : 31 글 내용 : 한달 후 글
글 넘버 : 365 글 내용 : 1년후 글
글 넘버 : 3650 글 내용 : 10년후 글
 */

 

참고

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

https://coding-factory.tistory.com/603