Java 우선순위 큐(Priority Queue)

큐(Queue)

먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 자료구조의 한 형식이다.

 

우선순위 큐(Priority Queue)

먼저 들어온 것부터 먼저 나가는 일반적인 큐(선형 또는 원형)와 다르게 우선순위를 결정하고 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조이다.

• 높은 우선순위의 요소가 먼저 나와야 하므로 큐에 들어가는 요소는 비교 가능한 기준이 있어야 한다.
• 배열이나 연결리스트가 아닌 힙(heap)이라는 자료구조로 구현한다.
• 내부 구조는 이진트리로 구성되어 있다.
• 힙 자료구조는 부모 노드는 자식 노드보다 항상 우선순위가 앞선다는 조건을 만족시키며 완전 이진트리를 만드는 것이다.

🧐 힙(heap) 자료구조
우선순위 큐는 힙 자료구조를 이용하여 구현된다.
힙은 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조이다.
이진트리는 모든 노드의 최대 차수를 2로 제한한 트리구조(자식 노드를 최대 2개만 가질 수 있음)이고, 완전 이진트리를 만족하기 위해서는 마지막 레벨을 제외한 모든 노드가 왼쪽부터 채워져 있어야 한다.
이진트리와 다르게 중복 값이 허용된다.

우선순위 큐에 값을 추가하면 일단 마지막에 넣고 부모와 비교해서 작으면 교환하여 오른쪽과 같은 최소 힙 트리를 만들게 된다.

우선순위 큐에서 값을 제거하려면 루트 노드와 마지막 노드를 스왑하여 사이즈를 줄여 자식 노드 두 개를 비교하는 과정을 반복하여 제거한다. 최대 힙 트리는 최소 힙 트리와 반대로 부모 노드가 자식 노드보다 큰 값을 만족하는 트리이다.

 

우선순위 큐 사용 방법

선언

// 우선순위가 낮은 숫자 순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 우선순위가 높은 숫자 순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

삽입

priorityQueue.add(1);	// 큐가 꽉 차면 예외 발생
priorityQueue.offer(1);	// 큐가 꽉 차면 실패를 의미하는 false 리턴

제거

priorityQueue.peek();		// 첫 번째 값 반환(제거X)
priorityQueue.poll();		// 첫 번째 값을 반환 & 제거
priorityQueue.remove();		// 첫 번째 값을 제거
priorityQueue.clear();		// 초기화

 

참고자료 및 출처 🙇‍♂️

https://st-lab.tistory.com/205

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