[Java] priority Queue(우선 순위)

 

코딩 테스트를 공부하면서 우선순위를 두는 문제를 풀었던 경험이 있다.

이때 나는 List 를 사용하여 naturalOrder 을 통해 자연순서 정렬을 하여 풀었는데

다른사람 풀이에서 priority Queue 라는 것을 접하게 되었다

더욱 편리하고 간단해서 공부해 보았다.

 

 

---

 

Priority Queue 특징

 

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다. 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 한다.
• 내부 요소는 힙으로 구성되어 이진트리 구조이다.
• 내부구조가  힙으로 구성되어 있기에 시간 복잡도는  O(NLogN)이다.
• 우선순위를 중요시해야 하는 상황에서 주로 쓰인다.

Priority Queue 선언

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

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

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

Priority Queue 데이터 삭제

 

queue.remove() 

큐의 첫번째 요소를 삭제 및 반환한다.

큐가 비어있다면 예외 발생.

queue.poll()

큐의 첫번째 요소를 삭제 및 반환한다.

큐가 비어있다면  null 반환

 

queue.clear()

큐의 모든 요소를 삭제

반환 타입 void

 

 

Priority Queue 데이터 추가

 

                           

 add()

• 해당 큐 맨 뒤에 값 삽입
• 값 추가 성공 시 true 반환
• 큐가 꽉 찬 경우 IllegalStateException 에러 발생

offer()

• 해당 큐 맨 뒤에 값 삽입
• 값 추가 성공 시 true 반환
• 값 추가 실패 시 false 반환

 

Priority Queue 맨 앞 데이터 확인

 

1. element()

• 큐의 맨 앞에 있는 값 반환
• 큐가 비어 있는 경우 NoSuchElementException 에러 발생

2. peek()

• 큐의 맨 앞에 있는 값 반환
• 비어있을 경우 null 반환