우선순위 큐 (Priority Queue)

우선순위 큐 (Priority Queue)

우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 기존의 기본 큐는 가장 먼저 삽입된 데이터를 가장 먼저 삭제하는데 우선순위 큐는 우선순위에 따라 삭제한다. 따라서, 우선순위에 따라 처리하고 싶을때 사용한다. 

 

우선순위 큐는 힙 자료구조로 구현되어있다.  자바에서는 아래 라이브러리로 사용이 가능하다.

 

import java.util.PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

 

큐 라이브러리에 데이터를 묶음으로 넣으면, 첫번째 원소를 기준으로 우선순위를 설정한다. 우선순위 큐를 사용하면 내부적으로 최소 힙, 최대 힙을 이용한다. 최소 힙을 사용하는 경우 '값이 낮은 데이터가 먼저 삭제'된다. 최대 힙을 이용하는 경우 '값이 큰 데이터가 먼저 삭제'된다. 

 

예를들어, 다익스트라 알고리즘과 같이 비용이 적은 노드를 우선 방문하는 경우에 최소 힙 구조를 기반으로 사용한다. 

 

* 최소 힙을 최대 힙처럼 사용하는 방법
우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(=)를 붙여서 원래의 값으로 돌리는 방식으로 사용할 수 있다.

 

 

 

 

구현 코드

package Y19_ShortestPath.PriorityQueue;

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // PriorityQueue 를 사용해서 숫자가 작을수록 우선순위를 가지게 저장
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        int[] arr = new int[]{5, 7, 3, 1, 2};

        for (int v : arr) {
            pq.add(v);
        }

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

 

결과

1
2
3
5
7

 

 

 

 

 

사용 예제

우선순위 큐를 사용한 풀이를 참고하자.

https://devfunny.tistory.com/490

[프로그래머스] Level2 _42626번: 더 맵게 (JAVA)