[자료구조] 자바 우선순위 큐(Priority Queue)의 클래스 사용하기

 Priority Queue

• 일반적인 큐의 구조 FIFO (First In First Out)을 가진다.
• 우선순위를 먼저 결정하고, 우선순위가 높은 데이터가 먼저 나가는 구조이다.
• 우선순위 큐를 사용하기 위해 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.
• Comaprable Interface 구현 시 compareTo method 를 override 하여 처리할 우선순위 조건을 리턴하면, 우선순위 큐가 우선순위가 높은 객체를 추출해준다. (기본적으로 낮은 숫자부터 큰 숫자 오름차순이다)
• Heap을 이용하여 구현하는 것이 일반적이다.
• 데이터 삽입 시 우선순위 기준으로 최대 힙, 최소 힙을 구성한다.
• 데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입 후 아래 노드로 내려가면서 정렬하는 방식으로 진행된다.
• 최대 힙 = 최대 값이 우선순위인 큐 
• 최소 힙 = 최소 값이 우선순위인 큐

 

주로 사용하는 메서드

public class PriorityQueue<E> extends AbstractQueue<E> 
	implements java.io.Serializable {
	
	public PriorityQueue();
	public PriorityQueue(Comparator<? super E> comparator);
	public boolean offer(E e);
	public boolean remove(E e);
	public E poll();
	public E peek();
	public int size();
	public void clear();
	public isEmpty();
	    
}

 offer 메서드

우선순위큐에 원소를 삽입하는 메서드이다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);
pq.offer(3);
pq.offer(2);
// pq : [1,2,3]

 remove 메서드

파라미터 값을 탐색하여 일치하는 원소를 제거한다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(4);
pq.offer(1);
pq.offer(2);
pq.offer(3);
        
System.out.println(pq.remove(3));

 poll 메서드

우선순위 큐의 머리 부분의 원소를 제거한 후 해당 원소를 반환한다.

우선순위 큐가 비어있는 경우 null을 반환한다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);
System.out.println(pq.poll());	// output : 1
System.out.println(pq.poll());	// output : null

 peek 메서드

우선순위 큐의 머리 부분의 원소를 제거하지 않고 해당 원소를 반환한다.

우선순위 큐가 비어있는 경우 null을 반환한다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);
System.out.println(pq.peek());	// output : 1
System.out.println(pq.poll());	// output : 1
System.out.println(pq.peek());	// output : null

 clear 메서드

우선순위 큐에 존재하는 모든 원소를 모두 삭제한다. (초기화)

 isEmpty 메서드

우선순위 큐에 원소가 존재하면 false, 존재하지 않으면 true 반환한다.

 

 

 Priority Queue 생성 예제

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

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

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

 

 

우선순위 큐 출력(Sysout) 시 정렬이 된거 맞아??

실제로 아래와 같이 구현을 한 뒤 pq 를 출력하면 [1,3,2,3] 으로 표출된다.

Comparable 인터페이스를 구현하지 않으면, 기본적으로는 오름차순 정렬이 아닌가?

우선순위 큐는 Heap 자료구조의 원리를 사용하고 있어 삭제나 조회등의 메서드를 호출했을 때, 루트 노드를 기준으로 이루어진다. 그렇기 때문에 루트 노드외에는 정렬이 되어있지 않다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);
pq.offer(4);
pq.offer(2);
pq.offer(3);

System.out.println(pq);	// output : [1,4,2,3]

우선순위 큐에 첫 번째로 '3'을 넣어도 pq 를 출력하면, 가장 우선순위인 '1', 즉 루트노드만 정렬되어있는 것을 볼 수 있다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(4);
pq.offer(1);
pq.offer(2);
pq.offer(3);

System.out.println(pq);	// output : [1,4,2,3]