PriorityQueue ( 우선순위큐 )

우선순위 큐

일반적인 큐 구조를 가지면서, 데이터가 들어온 순서대로 나가는것이 아닌 우선순위를 먼저 결정하고

우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

 

 

 

우선순위 큐의 조건

필수적으로 Comparable Interface를 구현해야 한다.

 

 - Comparable Interface를 구현하면 compareTo method 를 오버라이딩하게 되고,

    객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 알아서 우선순위 높은 객체를 추출하는 구조입니다.

 

Heap 을 이용해 구현하는 것이 일반적입니다.

 

 - 데이터를 삽입할 때  우선순위를 기준으로 최대 힙 또는 최소 힙을 구성합니다.

    데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입 후 아래로 내려가면서

    적절한 위치를 찾아 옮기는 방식으로 진행됩니다.  ( * 최대힙과 최소힙 * )

 

 

우선순위 큐 특징

1. 높은 우선순위의 요소를 먼저 꺼내 처리하는 구조입니다.

2. 내부 요소는 힙으로 구성되어 이진트리 구조를 가집니다.

3. 우선순위를 중요시해야하는 상황에 주로 쓰입니다.

4. 시간복잡도는 O(NlogN) 입니다.

 

 

 

우선순위 큐 선언

Priority Queue 를 사용하면 java.util.PriorityQueue 를 import 합니다.

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

 

 

 

우선순위 큐 동작 방법

// add(value) 메서드의 경우 만약 삽입에 성공하면 true를 반환, 
// 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생
priorityQueueLowest.add(1);
priorityQueueLowest.add(10);
priorityQueueLowest.offer(100);

priorityQueueHighest.add(1);
priorityQueueHighest.add(10);
priorityQueueHighest.offer(100);


// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();

// 초기화
priorityQueueLowest.clear();