[java] PriorityQueue 우선순위 큐 사용하기
📌PriorityQueue 알아보기
◾PriorityQueue 란
우선순위를 기반으로 요소들을 저장하고 관리하는 자료구조이다. 큐(Queue)의 일종으로, 각 요소는 특정 순서에 따라 우선순위를 갖게 되며, 우선순위가 높은 요소가 먼저 처리된다.
◾PriorityQueue 특징
- 우선순위: 각 요소는 우선순위를 가지며, 기본적으로 작은 값이 높은 우선순위를 나타낸다.
(Comparable인터페이스 또는 별도의 Comparator를 사용하여 지정이 가능하다.)
- 최소 힙 구조: PriorityQueue는 일반적으로 최소 힙(Main Heap)구조로 구현되어 있다.
- 삽입 및 삭제: 요소는 삽입될 때 우선순위에 따라 정렬되며, 가장 우선순위가 높은 요소가 항상 루트에 위치한다.
- 시간복잡도:
요소 삽입 : O(log n)
요소 삭제 및 반환 : O(log n)
Peek(가장 우선순위가 높은 요소 확인) : O(1)
◾PriorityQueue 사용하기
1. 선언하기
1-1 최소힙
: 가장 작은 값이 우선순위가 높으며, 이 값이 루트노드에 위치한다.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
1-2 최대힙
: 가장 큰 값이 우선순위가 높으며, 이 값이 루트노드에 위치한다.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
2. 값 추가하기
minHeap.add(4);
minHeap.offer(9);
minHeap.add(2);
minHeap.offer(1);add(), offer()은 기본적으로 동일한 기능을 수행한다. 차이는 아래와 같다.
- add(값): 큐에 요소를 추가하며, 큐가 꽉 찬 경우 예외를 발생시킬 수 있다.
- offer(값): 큐에 요소를 추가하며, 큐가 꽉 찬 경우 예외를 발생시키지 않고 false를 반환한다.
3. 값 꺼내기, 제거하기
3-1 단일 값
// 현재 큐에 1,2,4,9가 존재하는 상태이다.
int highestPriority = minHeap.poll(); // 1 return 후 제거
boolean removed = minHeap.remove(9); // 특정 요소를 제거
int objectRemoved = minHeap.remove(); // 2 return 후 제거poll()과 remove() 모두 요소를 제거하며 반환하는 역할을 한다. 차이는 아래와 같다.
- poll(): 큐에서 가장 우선순위가 높은 요소를 제거하고 반환한다.
poll()을 사용할 때는 반환된 값이 null인지 체크하여 큐가 비어있는지 여부를 확인하는게 좋다.
요소가 없을 경우 예외를 발생시키지 않고, `null`을 반환한다.
- remove(): 큐에서 가장 우선순위가 높은 요소를 제거하고 반환한다. 큐가 비어있다면 NoSuchElementException예외를 발생시킨다.
- remove(특정 값): 특정 요소를 제거한다. 특정 값이 있을 경우 true를, 그렇지 않을 경우 false를 반환한다 .
3-2 모든 값 제거
minHeap.clear();clear(): 우선순위 큐에서 모든 값이 제거되어 빈 상태가 된다.
4. 값 가져오기
int highPriority2 = minHeap.peek();peek(): 우선순위 큐의 가장 우선순위가 높은 요소를 반환한다. 큐에서 요소를 제거하지 않고 단순히 확인 용도로 사용된다.
5. 우선순위 큐 순회하기
while (!minHeap.isEmpty()) {
int element = minHeap.poll();
System.out.println(element);
}우선순위 큐는 내부적으로 정렬되어 있어 순회하면 높은 우선순대로 값을 얻을 수 있다.