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

우선순위 큐(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());

기본은 우선순위가 낮은 숫자가 부여되고

만약 높은 숫자가 우선순위가 되게 하고 싶다면 선언 시 Collections.reverseOrder() 메서드를 활용합니다.

 

 

우선순위큐 값추가.

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

우선순위 큐에 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 됩니다.

add(value) 메서드의 경우 만약 삽입에 성공하면 true를 반환하고,

큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킵니다.

 

 

우선순위큐에 값을 넣었을때 힙의 정렬 과정 ( 최소힙 경우)

7이 들어왔다고 가정, 들어온값은 가장 마지막 노드에 배치

부모노드와 비교해서 더 작으면 교환 swap(7,8)

부모와 비교했지만 값이 더 작지않아 교환X

우선순위큐 값 제거

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

우선순위 큐에서 값을 제거하고 싶다면 poll()이나 remove()라는 메서드를 사용하면 됩니다.

값을 제거할 시 우선순위가 가장 높은 값이 제거됩니다.

 

poll() 함수는 우선순위 큐가 비어있으면 null을 반환합니다.  [비어있지않다면 해당값을 리턴해주고 삭제한다.]

pop을 하면 우선순위가 가장높은값이 제거가 된다.

queue의 모든 요소를 제거하려면 clear() 메서드를 사용합니다.

 

우선순위큐에서 값을 제거 후 정렬 과정 ( 최소 힙 기준)

삭제를 하기전 최소힙 상태

queue.pop() 을 하게 된다면

마지막노드인 8을 루트에 놓고 루트노드였던 1은 빼준다.

루트노드부터 자식노드와 비교를 들어간다.

자식노드인 7이 더 작으므로 자리를 바꾼다 swap(7,8)

 

자리를 바꾼후 다시한번 자식노드와 비교한다 ( 값이 더 작으므로 변경 x)

우선순위가 높은값 출력

Peek()메소드를 이용하여 값을 제거하지않고 현재 가장 우선순위가 높은 값을 뽑아낼 수 있다.

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

peek()의 반환은 Wrapper타입이며, 값이 없을경우 null을 리턴해준다. 

 

우선순위큐 시간복잡도

우선순위가 높은 값 조회 -> O(1)

 

우선순위큐의 삽입,삭제연산 -> O(logN)

 

N개의 수에 대해 우선순위큐에 삽입했을때 -> O(NlogN)

 

따라서 우선순위큐를 이용한 정렬에는 시간복잡도 O(NlogN)이 걸린다.

 

 

 

 

 

우선순위큐를 출력해도 정렬된 결과를 얻을 수 없다.

최대힙,최소힙은 부모노드는 자식노드보다 우선순위가 높다는 기준하나로 정렬되어있으므로

형제노드끼리는 정렬이 되어있지않다.

그러므로 우선순위큐를 출력해도 정렬된 결과를 얻을 수없고,

우선순위가 가장높은 루트노드에 대한 결과를 이용하면 된다.

[Java] Heap, 힙 , 트리, 이진트리, 완전 이진트리

 

 

 

우선순위큐의 정렬기준을 자신이 만들 수도 있다.

absPriorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        if (Math.abs(o1) == Math.abs(o2)) { //절대값이 같다면
            return o1 - o2; // 값 자체로 비교해서 오름차순
        } else {
            return Math.abs(o1) - Math.abs(o2); // 아니면 절대값으로 비교해서 오름차순
        }
    }
});

이런식으로

예시 문제

https://keeeeeepgoing.tistory.com/127

백준/11286 절댓값 힙 / 우선순위큐, Comparator

 

https://keeeeeepgoing.tistory.com/64

[Java] Comparator , Comparable , 익명객체(클래스)

 

 

 

 

출처,더 자세한 정보

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