[java] Priority Queue

자바역시 C++ 처럼 우선순위 큐가 존재한다.

거두절미하고 소스부터 본다.

import java.util.PriorityQueue;
/*기본 생성자. 객체의 기본 비교 CompareTo를 사용한다.*/
PriorityQueue<Integer> pq=new PriorityQueue<>();
//기본 배열크기, 비교함수를 인자로 받는 생성자.
PriorityQueue<Integer> pq=new PriorityQueue<>(11,AAA::Compare);

add는 C++ 의 push와 같은 역할을 한다.
poll 은 C++ 의 top+pop이다.
peek 는 C++의 top 이다.

이 3가지 연산이 주로 사용된다.

아래는 우선순위 큐를 이용한 다익스트라의 예시이다.

import java.util.*;
public class Main {
    static public ArrayList<ArrayList<Map.Entry<Integer,Integer>>> G;
    static public Integer[] D;
    static public Integer V,E,K;
    static public final Integer INF=987654321;
    public static void main(String[] args){
        /*...*/
    }
    public static int compare(Map.Entry<Integer,Integer> a
                             ,Map.Entry<Integer,Integer> b){
        return a.getKey()<b.getKey()?-1:a.getKey()>b.getKey()?1:0;
    }
    public static void dijkstra(){
        D=new Integer[V];
        Arrays.fill(D,INF);
        D[K]=0;
        //cost, to
        PriorityQueue<Map.Entry<Integer,Integer>> pq=
                 new PriorityQueue<>(11,Main::compare);
        pq.add(new AbstractMap.SimpleEntry<>(0,K));
        while(pq.isEmpty()==false){
            Map.Entry<Integer,Integer> min=pq.poll();
            //해당 정점의 간선을 순회
            for(int i=0;i<G.get(min.getValue()).size();i++){
                int to=G.get(min.getValue()).get(i).getKey();
                int cost=G.get(min.getValue()).get(i).getValue();
                if(D[to] > D[min.getValue()] + cost){
                    D[to] = D[min.getValue()] + cost;
                    pq.add(new AbstractMap.SimpleEntry<>(D[to],to));
                }
            }
        }
    }
}