자바 PriorityQueue

자바 코딩테스트 공부 중 백준 11286 절댓값 힙 문제를 푸는 중에 Priority Queue 을 사용하는 방법에 대해 간단하게 정리해보려고 합니다. 이 포스팅에서는 매우 간단한 사용 방법을 설명합니다.

 

추가로 PriorityQueue 의 인자로 comparator 을 가질 수 있는데 이 부분은 오른쪽 링크 https://sh1mj1-log.tistory.com/122 포스팅하단에서 확인할 수 있습니다.

 

 

Priority Queue(우선순위 큐)?

Priority Queue 는 Queue 와 구조가 비슷합니다.

Queue 는 FIFO(First In First Out) 구조로 먼저 들어온 순서대로 데이터가 나가는 것인 반면에

Priority Queue 는 데이터의 우선순위를 정해 우선순위가 높은 순서대로 데이터가 나가는 것입니다. Priority Queue 는 우선순위 힙으로 구현을 할 수 있습니다. 데이터를 삽입할 때 우선순위의 최대, 최소를 구성하여 데이터가 빠지면 중간을 계속해서 채워넣는 방식입니다.

 

 

위 그림에서의 우선순위 큐는 Int 값 중 가장 큰 수가 우선순위가 높은 것으로 되어있습니다. 물론 항상 수의 값이 큰 것 혹은 작은 값이 우선순위가 높은 것이 아니라 프로그래머가 정할 수 있는 것입니다.

 

Priority Queue 특징

우선순위 큐는 값을 비교해야 하므로 `null` 을 허용하지 않습니다. 또 객체는 우선순위를 비교하기 어려우므로 보통 Priority Queue 로 만들지 않습니다.

 

내부 구조는 이진 트리 힙으로 구성되어 있습니다. 그러므로 add() 및 poll() 메서드에서 `O(log(n))` 의 시간이 걸립니다.

자바에서는 가까운 계층 순서대로 AbstractQueue, AbstractCollection, Collection, Object 클래스에서 메서드를 상속합니다.

 

Priority Queue 사용법

 

Priority Queue 선언

// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정 (오름차순) - 최소힙)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정 (내림차순) - 최대힙)
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());

// String 타입으로 우선순위 큐 선언(낮은 String 순으로 우선순위 결정 ex: abc 가 bca 보다 먼저)
PriorityQueue<String> priorityQueue3 = new PriorityQueue<>();

// String 타입으로 우선순위 큐 선언(높은 String 순으로 우선순위 결정 ex: bca 가 abc 보다 먼저)
PriorityQueue<String> priorityQueue4 = new PriorityQueue<>(Comparator.reverseOrder());

 

구조를 보면 선언하는 부분은 쉽게 이해할 수 있습니다.

 

기억해야할 부분은 자바에서 PriorityQueue 는 낮은 숫자 순으로 우선순위를 결정하는 최소힙 정렬이 Default 입니다!!

 

Priority Queue 값 추가

// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
priorityQueue1.add(1);
priorityQueue1.add(9);
priorityQueue1.add(10);
priorityQueue1.add(2);
priorityQueue1.add(12);
priorityQueue1.add(5);
priorityQueue1.add(4);
System.out.println(priorityQueue1);

---

출력:

[1, 2, 4, 9, 12, 10, 5]

---

우선순위 큐에 값을 추가하는 방법은 add(), offer() 가 있습니다.

add() 는 Collection 클래스의 메서드, offer() 는 Queue 클래스에서 가져오는 메서드입니다.

출력 결과는 우선순위 큐 만의 정렬 방식으로 정렬됩니다.

Priority Queue 의 동작은 아래처럼 동작합니다.

 

 

1.1 우선순위 큐의 삽입

• 삽입할 원소는 완전 이진트리를 유지하는 형태로 순차적으로 삽입됩니다.
• 삽입 이후에는 루트 노드까지 거슬러 올라가면서 최소힙을 구성합니다.(상향식)
• 즉, 부모노드와 비교를 해서 부모노드가 삽입한 노드의 값보다 크다면 교체합니다.(logN의 시간복잡도를 가진다)

여기서 처음 삽입할 때 노드 10의 자식은 4와 5의 순서는 랜덤하게 정렬됩니다. 그래서 출력할 때마다 자식 노드는 최소힙(또는 최대힙)을 만족하기만 하면 약간은 랜덤하게 출력될 수 있습니다.

 

 

Priority Queue 값 삭제

// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();

priorityQueue1.add(1);
priorityQueue1.add(9);
priorityQueue1.add(10);
priorityQueue1.add(2);
priorityQueue1.add(12);
priorityQueue1.add(5);
priorityQueue1.add(4);
System.out.println(priorityQueue1);

priorityQueue1.poll();
System.out.println(priorityQueue1);

priorityQueue1.remove();
priorityQueue1.remove(1);
System.out.println(priorityQueue1);

priorityQueue1.clear();
System.out.println(priorityQueue1);

 

poll() , remove() 메서드를 사용하면 우선순위가 가장 높은 값을 제거합니다. clear() 메서드를 사용하면 우선순위 큐의 모든 값을 삭제합니다.

결과
[1, 2, 4, 9, 12, 10, 5]
[2, 5, 4, 9, 12, 10] // poll()
[4, 5, 10, 9, 12] // remove(), remove(1)
[] // clear

 

만약 첫번재 우선순위를 삭제하게 되면 큐의 값이 하나씩 밀리는 것이 아닌 우선순위을 재정렬합니다.

 

 

• 루트 노드인 1 과 마지막 노드인 5가 스왑됩니다.
• 루트 노드였던 1은 제거됩니다.
• 그리고 변경된 노드들을 순차적으로 검사합니다. 위에서는 루트노드에 있는 5가 자식 노드보다 큰 값이므로 두 값을 비교해서 작은 값과 스왑합니다. 이렇게 다시 최소힙을 만족하게 됩니다.

즉, 이렇게 다시 우선순위가 정렬되는 것이지요.

Priority Queue 크기, 값 출력

// Priority Queue 의 크기
priorityQueue1.size()

// Priority Queue 값 출력
System.out.println(priorityQueue1.peek());

Iterator iterator = priorityQueue1.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

 

결과
1
1 2 4 9 12 10 5

 

Priority Queue 에서 peek() 메서드를 사용하면 우선순위가 가장 높은 값을 출력합니다.

iterator 을 사용하여 위처럼 전체 Queue 의 값을 출력할 수 있습니다.

 

 

https://crazykim2.tistory.com/575

https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.programiz.com%2Fdsa%2Fpriority-queue&psig=AOvVaw1vC6v_rM9Wv_L6HZXRt-Nx&ust=1685406189718000&source=images&cd=vfe&ved=0CBEQjRxqFwoTCLiI07uhmf8CFQAAAAAdAAAAABAE

https://velog.io/@holicme7/우선순위-큐Prioirity-Queue-mbk48cz764