[자료구조] 우선순위 큐(priorityQueue) 알아보기 (with 자바)

 

---

우선순위 큐(priorityQueue) 란?

우선순위 큐(Queue)란? 우선순위 큐는 평범한 큐(queue)나 스택(stack)과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있어 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 내부 요소는 힙으로 구성되어  있어 시간 복잡도는 O(NLogN)이며,  이진트리 구조로 이루어져 있다.

 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다. 즉, 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다. 

Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다.

PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.

 

Priority Queue 동작

추가(Add)

https://coding-factory.tistory.com/603

 

 

삭제(Remove)

https://coding-factory.tistory.com/603

 

---

자바 Priority Queue 사용해보기

Priority Queue 선언

/**
 * 우선 순위가 오름차순인 최소 힙 우선순위 큐
 * import java.util.PriorityQueue
 * */
PriorityQueue<Integer> minPriorityQueue = new PriorityQueue<>();

/**
 * 우선 순위가 내림차순인 최대 힙우선순위 큐
 * import java.util.Collections
 * */
PriorityQueue<Integer> maxPriorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

Priority Queue 값 추가

minPriorityQueue.add(1);
minPriorityQueue.add(10);
minPriorityQueue.add(3);
minPriorityQueue.offer(20);

 

Priority Queue 값 삭제

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

출력
1
1
3

 

Priority Queue 값 초기화

minPriorityQueue.clear();      // priorityQueue에 초기화

 

 

---

참고한 자료

🌈 자료구조:: 우선순위 큐(Priority Queue)

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

[JAVA] Priority Queue(우선순위 큐) 개념 및 사용법 정리