작성일 2024.2.17

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

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