PriorityQueue와 Comparator

YeJi Kim·2023년 3월 10일

JAVA

목록 보기

4/5

최대힙, 최소힙을 이용한 PriorityQueue에 대해 살펴보자! 🤓
또한 PriorityQueue와 함께 사용되는 Comparator에 대해서도 알아보자! 🤓👊

PriorityQueue

PriorityQueue는 priority heap을 기반으로 한 무제한 우선순위 큐이다.
PriorityQueue는 생성자의 매개변수로 전달된 natural ordering이나 Comparator에 의해 정렬된다.
PriorityQueue는 null을 요소로 허용하지 않으며 비교할 수 없는 객체의 삽입을 허용하지 않는다. 생성자에 아무것도 지정하지 않으면 내부 요소들을 오름차순으로 정렬한다.

큐의 head는 가장 작은 요소를 가리키고 있다. 최소값을 위해 여러 요소가 묶인 경우, head는 이들 요소 중 하나만을 가리키고 있다.

PriorityQueue에 요소가 추가되면 해당 용량이 자동으로 증가한다.
PriorityQueue는 동기화되지 않은 클래스이다. 만약 멀티 스레드 환경에서 PriorityQueue가 사용되어 동기화가 필요하다면 PriorityBlockingQueue 클래스를 대신 사용해야 한다.

PriorityQueue는 들어갈 때는 순서가 없지만 나올때는 순서대로 뽑혀 나온다.

참고 자료
분명히 정렬이 된다고 하였는데 왜 정렬되지 않은 형태로 출력이 될까요? 게다가 값을 집어넣은 순서와도 다릅니다. 왠지 불안해지는데요? 하지만 사실 걱정할 필요는 없습니다. 나중에 값을 꺼내다 보면 가장 작은 값부터 오름차순으로 값이 꺼내지니까요.
우선순위 큐는 힙을 사용하여 구성하며 내부 구조는 이진트리 형태로 구성되어있습니다. 값을 삽입할 때 가장 마지막에 넣은 후, 자신보다 작은 부모노드를 찾을 때 까지 이동시키는 과정을 통해 값의 위치를 정합니다. 무엇보다 이진트리 형태로 저장되기 때문에 출력 당시에는 오름차순이 아닌 형태로 보여질 수도 있는 것이지요. 정말 간략하게 원리에 대해서 설명해 보았습니다. 늘 그랬듯 원리는 그다지 중요하지는 않습니다. 확실히 알아야 할 것은 값을 넣은 순서가 아니라, 오름차순으로 값이 꺼내진다는 것이니까요.

출처: https://wikidocs.net/122046

PriorityQueue의 시간복잡도

삽입과 삭제 메서드(offer, poll, remove, add)의 시간복잡도는 O(log n)이다.
remove(Object)와 contains(Object) 메서드는 Object 값을 찾기 위해 N만큼 반복하므로 선형 시간복잡도 O(N)을 갖는다.
retrieval 메서드(peek, element, size)는 입력 크기에 구애받지 않고 어떤 값에 한정되기 때문에 상수 시간복잡도 O(1)을 갖는다.

PriorityQueue의 메서드

Comparator

Interface Comprator는 함수형 인터페이스이기 때문에 람다식 또는 메서드 참조에 사용될 수 있다.
Comparator는 개체 집합의 전체를 정렬하는 비교 함수이다. Comprator는 정렬 메서드(예를 들어, Collections.sort와 Arrays.sort)에서 정렬 순서를 제어하기 위해 사용될 수 있다.
Comparator는 sorted sets이나 sorted maps와 같은 특정 데이터 구조의 순서를 제어하기 위해 사용되거나 natural ordering을 제공하지 않는 컬렉션을 정렬하기 위해 사용될 수 있다.

Comprator 클래스의 compareTo()는 두 객체를 비교하는 메서드이다. compareTo()의 반환값은 int이지만 실제로는 비교해야 하는 두 객체가 같으면 0, 비교하는 값보다 작으면 음수, 크면 양수를 반환하도록 구현해야 한다.

Comparator는 함수형 인터페이스이고 함수형 인터페이스에는 오직 하나의 추상 메서드만 정의되어 있어야 한다는 제약이 있다. 함수형 인터페이스는 람다식과 인터페이스의 메서드가 1:1로 연결될 수 있기 때문에 람다식으로 대체될 수 있다.