[Data Structure] Priority Queue - 우선순위 큐

Priority Queue

---

Priority Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. Queue와 구조가 비슷할 것 같지만 둘은 많은 차이가 있다. Queue는 연산의 결과로 FIFO 즉, 먼저 들어간 데이터가 먼저 나오지만 Priority Queue는 그렇지 않다. 앞서 설명한 것처럼 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

Priority Queue는 Array, List, Heap으로 구현할 수 있다. 하지만 Array와 List는 데이터 삽입과 삽입 위치를 찾는 과정에서 성능을 저하시킬 수 있기때문에 일반적으로 Heap을 이용해 구현한다. Priority Queue의 개념은 사실상 Heap에 대한 개념과 같기 때문에 Heap에 대한 이해가 부족하다면 아래 글을 먼저 읽고 오면 좋다.

 

https://zzzzseong.tistory.com/17

[Data Structure] Heap

 

 

Java에서 Priority Queue의 사용

---

Priority Queue의 매커니즘이 Heap의 매커니즘과 다름없기 때문에 알고리즘의 동작 방식은 생략하고 바로 Java에서 Priority Queue를 활용하는 방법에 대해 알아보겠다.

 

Priority Queue 선언

Heap에서 Min-Max Heap이 있기에 Priority Queue에서도 우선순위를 결정할 수 있다. 아래와 같이 Priority Queue를 선언해 우선순위의 방향을 설정할 수 있다.

 

기본적인 Priority Queue 사용

Priority Queue에 데이터를 추가하고 삭제하는 방법은 아래와 같다. add() 함수를 사용해 값을 추가하고 remove() 함수를 사용해 값을 삭제한다. pq의 설정이 default이기 때문에, 아래를 보면 데이터를 불규칙적으로 삽입해도 삭제 시 값이 작은 원소 순서로 삭제된다. isEmpty()는 pq가 비어있는지 확인하는 함수이다.

 

현재 Priority Queue에 들어가있는 데이터의 갯수는 size() 함수로 확인할 수 있다. 또한, clear() 함수를 이용하면 pq에 들어있는 값을 초기화 할 수 있다.

 

객체와 함께 Priority Queue 사용

정수를 Priority Queue에 넣고 꺼낼때는 기본적으로 제공하는 함수를 통해 쉽게 기능을 사용할 수 있다. 하지만, 사용자가 정의한 객체를 Priority Queue에 넣고 싶을때는 어떻게 해야할까? Priority Queue의 선언부에 Comparator를 정의해줘야한다. 예제를 위해 아래와 같이 Member Class와 MemberComparator를 선언했다.

 

Priority Queue에 Member 객체를 삽입했을때 point가 작은 순서대로 삭제되는 것을 볼 수 있다. 또한, point가 아닌 name의 길이, 사전 순서대로 정렬을 하고 싶다면 Comparator를 조건에 맞게 수정해서 사용하면 된다.

 

 

[ 참고자료 ]

[JAVA] PriorityQueue 우선순위 큐 사용법