[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);
        }

우선순위 큐는 내부적으로 정렬되어 있어 순회하면 높은 우선순대로 값을 얻을 수 있다.