[Data Structure] Priority Queue(우선순위 큐) Java로 구현하기

Priority Queue(우선순위 큐)란?

일반적인 큐의 구조 FIFO(First In First Out)을 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌, 각 요소들이 각각의 우선순위를 갖고있고, 요소들의 대기열에서 우선순위가 높은 요소가 먼저 제공되는 자료구조

Priority Queue를 사용하기 위해서는 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

Comparable Interface를 구현하면 compareTo 메서드를 오버라이드하게 되는데 해당 객체에서 처리할 우선순위 조건을 리턴해주면 Priority Queue가 알아서 우선순위가 높은 객체를 추출해주는 것이다.

우선순위 큐를 구현하는데 있어 대표적인 구현 방식이 힙을 이용하는 방식이다.

 

힙(Heap)이란?

최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조

* 최대 힙 : 최대 값이 우선순위인 큐, 최소 힙 : 최소 값이 우선순위인 큐

 

Priority Queue 특징

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

 

Priority Queue 선언

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());

기본은 우선순위가 낮은 숫자가 부여되고, 만약 높은 숫자가 우선순위가 되게 하고 싶다면 Collections.reverseOrder() 메서드 활용

 

Priority Queue 메서드

기본적으로 Queue와 같다.

메서드	설명
public boolean add(E e)	삽입에 성공하면 true 반환 삽입에 실패하면 IllegalstateException 발생
public E element()	삭제없이 요소를 읽어옴 peek와 달리 Queue가 비었을 때 NoSuchElementException 발생
public boolean offer(E e)	Queue 에 객체를 저장 성공하면 true, 실패하면 false 반환
public E peek()	삭제없이 요소를 읽어옴 Queue 가 비어있으면 null을 반환
public E poll()	Queue 에서 객체를 꺼내서 반환. 비어있으면 null을 반환
public boolean remove(Object o)	Queue 에서 객체를 꺼내 반환 비어있으면 NoSuchElementException 발생
public boolean contains(Object o)	현재 찾고자하는 요소가 큐에 들어가있는지를 알려줌
size	현재 큐에 있는 요소의 개수를 알려줌
isEmpty	현재 큐가 비어있는지 확인 요소의 개수가 0개라면 비어있다는 뜻 비어있다면 true를, 비어있지 않다면 false를 반환
clear	초기화. Queue의 모든 요소를 비움

 

1. Priority Queue 값 추가

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가

우선순위 큐에 값을 추가한다면 아래와 같은 과정을 통해 즉시 정렬이 된다.

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

 

1. Priority Queue 값 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

pop을 하면 가장 앞쪽에 있는 원소의 값이 아래의 그림과 같이 제거된다.

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