[자료구조] 우선순위 큐(Priority Queue)

1. 개념

일반적인 큐의 구조를 가짐. 하지만 먼저 들어온 것이 먼저 나가는 구조가 아님. 

들어올 때 우선순위에 맞게 정렬이 되어 들어오고, 들어온 것들 중 정해놓은 우선순위가 가장 높은 것이 먼저 나가는 구조. 나가고 나서 우선순위에 맞게 다시 정렬이 됨.

 

2. 특징

• 값을 비교해야 하므로 null을 허용하지 않음
• 값을 비교해야 하므로 우선순위 큐에 삽입될 객체들은 Comparable Interface에 있는 compareTo 메서드가 구현되어 있는 객체여야 함.
• 내부 구조는 이진트리 힙으로 되어 있음
  • 값이 들어올 때 마다 일단 이진트리 맨 마지막에 값을 넣음
  • 그리고 부모 노드와 비교해가며 우선순위에 맞게 정렬을 진행함
  • 값이 나갈 때는 트리의 루트를 이진트리 맨 마지막 노드와 바꿈
  • 맨 마지막을 나가게 하고 루트와 자식을 우선순위에 맞게 정렬함
• 이진트리 구조이기 때문에 값을 추가하거나 삭제할 때 log(NlogN)의 시간복잡도를 가짐

 

3. 자바에서의 구현

1) 선언

java.util.PriorityQueue 를 import 하여 PriorityQueue 클래스를 사용. 기본적으로  값이 작은 것이 우선순위가 되어 정렬되어 있다. 만약 값이 큰 것이 우선순위가 되도록 정렬하고 싶다면 Collections.reverseOrder()를 선언해줘야 한다.

PriorityQueue<Integer> positiveNums = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> negativeNums = new PriorityQueue<>();
PriorityQueue<Integer> negativeNums = new PriorityQueue<>(2);// 우선순위 큐 초기 용량이 2가 되도록 선언

2) 우선순위 재정의

결과값이 양수면 앞에 있는 값이 더 크다는 것이고, 만약 작은 것이 우선순위 가지도록 되어 있으면 뒤에 있는 것이 우선순위가 되어 정렬됨, 뒤에 있는 것이 더 작으니까

결과값이 음수면 뒤에 있는 값이 더 크다는 것이고, 만약 작은 것이 우선순위 가지도록 되어 있으면 앞에 있는 것이 우선순위가 되어 정렬됨, 앞에 있는 것이 더 작으니까

 

Comparable 인터페이스의 compareTo() 를 오버라이딩

• 보통 사용자가 새로 만든 객체에 적용
• 우선순위 큐에 들어갈 객체 class 정의에 Comparable 인터페이스를 implements하고 compareTo() 메서드를 오버라이딩

Comparator 클래스를 사용하여 compare() 함수를 오버라이딩

• 이미 만들어져 있는 객체(Integer, Double 등)에 적용
  • 이미 비교 기준이 정의되어 있기에 비교 기준을 바꾸려면 Comparator을 써서 확장해줘야 함
• 특정 클래스의 생성자에 매개변수로 넣어서 구현

PriorityQueue<Integer> myQueue = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        int firstAbs = Math.abs(o1);
        int secondAbs = Math.abs(o2);
        if(firstAbs == secondAbs){
            return o1 > o2 ? 1 : -1;
        }else{
            return firstAbs - secondAbs;
        }
    }
});

• 람다식 이용

PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) -> {
    int firstAbs = Math.abs(o1);
    int secondAbs = Math.abs(o2);
    if(firstAbs == secondAbs){
        return o1 > o2 ? 1 : -1;
    }else{
        return firstAbs - secondAbs;
    }
});

 

4. 연산

1) add

값 추가. 추가 실패 하면 예외 발생

2) offer

값 추가. 추가 실패 하면 false 리턴

3) poll

우선순위 가장 높은 값을 리턴하면서 삭제. 비어 있는 큐에서 삭제하면 null 리턴

4) remove

우선순위 가장 높은 값 삭제. 비어 있는 큐에서 삭제하면 예외 발생

5) size

우선순위 큐의 사이즈 반환

6) peek

우선순위 큐 중 우선순위 가장 높은 값 출력

7) isEmpty

우선순위 큐가 비어있으면 true, 비어있지 않으면 false를 리턴

 

5. 관련 문제

백준 11286

GitHub - Lee-Min-Jung/coding_test_practice

백준 1715

GitHub - Lee-Min-Jung/coding_test_practice