6. 우선순위 큐(PriorityQueue)

개념

• 정의: 우선순위가 높은 대상이 먼저 나오는(pop) 자료구조
• 언제 사용?: 계속해서 선택지가 업데이트(추가)되는 상황에서 가장 최선의 값을 골라야하는 상황에 사용

 

구현 방법

리스트와 힙 방식이 있는데, 보통 heap을 이용해서 구현

우선 순위 큐 구현 방식	삽입(push) 시간	삭제(pop) 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

 

최소 힙 vs 최대 힙

• 최소 힙(오름차순): 가장 작은 값이 먼저 나오는 것
• 최대 힙(내림차순): 가장 큰 값이 먼저 나오는 것

 

사용법

java.util의 PriorityQueue 라이브러리 사용

 

기본형

초기화

//기본 타입 변수는 사용 불가
PriorityQueue<Integer> pq = new PriorityQueue<>();

 

삽입(offer)/추출(poll)

추출시 기본적으로 낮은 숫자가 추출

//삽입
pq.offer(3);

//추출
int a = pq.poll();

 

 

높은 숫자를 우선순위로 설정

낮은 숫자가 아닌 높은 숫자를 우선순위로 설정하고 싶을 때,

부호를 바꾸는 방식으로 진행

int a = 3;

//삽입 - 부호바꿔서 삽입
pq.offer(-a);

//추출 - 부호바꿔서 추출
int b = pq.poll();
System.out.println(-b);

 

 

객체형

우선순위 설정

• 객체를 우선순위에 넣는 경우 우선순위를 따로 설정해줄 필요가 있다.
• Comparable<> 클래스에 대한 구현체 생성
  • compareTo() 메서드 오버라이딩 진행
    • 1 반환: 우선순위가 더 낮다
    • -1 반환: 우선순위가 더 높다
    • 0 반환 : 우선순위가 동일하다

class Node implements Comparable<Node> {

    private int index;
    private int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Node other) {
        if (this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}

 

 

사용법

우선순위만 잘 설정하면 사용법은 기본형과 다르지 않다.

//초기화
PriorityQueue<Node> pq = new PriorityQueue<>();

//삽입
pq.offer(new Node(start, 0));

//추출
Node node = pq.poll();

 

 

원리

최소힙 - 새로운 원소가 삽입

• O(logN)의 복잡도
• 가장 마지막에 삽입 후
• 이후 마지막 노드에서부터 상향식으로 처리 진행

 

최소힙 - 원소 제거

• O(logN)의 복잡도
• 루트 노드에 있는 것을 삭제 후, 마지막 원소를 루트 노드에 위치
• 이후 루트 노드에서부터 하향식으로 처리 진행

루