힙 & 다익스트라

힙이란?

최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조

최대 힙 - 위키백과

최대 힙 : 부모 노드의 값 >= 자식 노드의 값

최소 힙 : 부모 노드의 값 <= 자식 노드의 값

- 힙은 배열을 이용해 구현할 수 있으며, 삽입 및 삭제 연산의 시간 복잡도는 힙의 높이에 따라 결정된다.

- 힙에서의 가장 높은(낮은) 우선순위가 항상 루트 노드에 오게 되기 때문에 이를 이용해 우선순위 큐로 사용한다.

메서드

자바에서는 따로 Heap 클래스가 존재하지 않으며 PriorityQueue를 통해 추상적인 자료구조로 사용할 수 있다.

import java.util.Collections;
import java.util.PriorityQueue;

public class TestPq {

    // 사용자 객체에 Comparable 인터페이스 구현(우선순위 큐에서 정렬하기 위한 compareTo 함수 Override필요)
    private static class Element implements Comparable<Element> {
        int dist, index;

        public Element(int dist, int index) {
            this.dist = dist;
            this.index = index;
        }

        @Override
        public int compareTo(Element e) {
            return this.dist - e.dist;   // dist 기준 오름차순 정렬
        }
    }

    public static void main(String[] args) {
        // 기본 오름차순
        PriorityQueue pq = new PriorityQueue();

        // 내림 차순
        PriorityQueue reversePq = new PriorityQueue(Collections.reverseOrder());

        // 사용자 생성 객체로 Pq 사용하
        PriorityQueue<Element> userPq = new PriorityQueue<>();

        // 우선순위 큐에 요소 추가
        // 요소는 우선순위에 따라 정렬되어 저장됩니다.
        pq.add(1);
        pq.add(2);
        
        // 용량 초과시 false 반환
        pq.offer(3);
        
        // 우선순위 큐의 최상단 요소를 제거하고 반환
        // 큐가 비어있다면 null을 반환
        pq.poll();

        // 우선순위 큐의 최상단 요소를 제거하지 않고 반환
        // 큐가 비어있다면 null을 반환
        pq.peek();

        // 우선순위 큐에서 특정 요소 제거
        // 요소 없으면 false 반환
        pq.remove(2);
                
        // 우선순위 큐에 특정 요소가 포함되어 있는지 확인
        pq.contains(1);

        // 우선순위 큐의 크기를 반환합니다.
        pq.size();

       
        
    }
}

 

스택 / 큐 / 우선순위큐(힙으로 구현한)의 연산별 시간복잡도

 

	스택 (Stack)	큐 (Queue)	우선순위큐 (Priority Queue)
삽입	​O(1)	O(1)​	O(log n)
삭제	​O(1)	​O(1)	O(log n)
최댓값/최솟값 얻기	​O(n)	​O(n)	O(1)

 

다익스트라 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Dijkstra {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();
    public static List<ArrayList<Node>> graph = new ArrayList<>();
    public static PriorityQueue<Element> pq = new PriorityQueue<>();
    public static int[] dist;
    static int N,M,start;

    // 그래프의 노드
    private static class Node {
        int w;
        int from;
        int to;

        public Node(int from, int to, int w){
            this.from = from;
            this.to = to;
            this.w = w;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "w=" + w +
                    ", from=" + from +
                    ", to=" + to +
                    '}';
        }
    }
    // pq로 비교할 누적값이 저장된 요소
    private static class Element implements Comparable<Element> {
        int dist, index;

        public Element(int dist, int index) {
            this.dist = dist;
            this.index = index;
        }

        @Override
        public int compareTo(Element e) {
            return this.dist - e.dist;   // dist 기준 오름차순 정렬
        }
    };
    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(br.readLine());
        N = Integer.parseInt(tokens.nextToken());
        start = Integer.parseInt(br.readLine());
        M = Integer.parseInt(tokens.nextToken());
        //초기화
        dist = new int[N+1];
        for(int i = 0; i <= N;i++){
            graph.add(new ArrayList<Node>());
        }
        for(int i = 1; i <= N; i++){
            dist[i] = (int)1e9;
        }
        dist[start] = 0;

        for(int i = 0; i < M;i++){
            tokens = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(tokens.nextToken());
            int to = Integer.parseInt(tokens.nextToken());
            int w = Integer.parseInt(tokens.nextToken());
            // 양방향이면 2개 해줘야됨
            graph.get(from).add(new Node(from,to,w));
            graph.get(to).add(new Node(to,from,w));
        }

        // 다익스트라.

        // 거리가 가까운 곳이 먼저 나와야 하며
        // 해당 지점이 어디인지에 대한 정보도 필요하므로
        // (거리, 정점 번호) 형태로 넣어줘야 합니다.
        pq.add(new Element(0,start));

        // O(|E|log|V|) 다익스트라 코드
        // 우선순위 큐에
        // 원소가 남아있다면 계속 진행해줍니다.
        while(!pq.isEmpty()){
            Element now = pq.poll();

            // 우선순위 큐를 이용하면
            // 같은 정점의 원소가
            // 여러 번 들어가는 문제가 발생할 수 있어
            // minDist가 최신 dist[minIndex]값과 다르다면
            // 계산할 필요 없이 패스해줍니다.
            if(now.dist != dist[now.index])continue;
            for(int i = 0; i < graph.get(now.index).size();i++){
                int target = graph.get(now.index).get(i).to;
                int w = graph.get(now.index).get(i).w;

                // 현재 위치에서 연결된 간선으로 가는 것이 더 작다면
                if(dist[now.index] + w < dist[target]){
                    // 값을 갱신해주고, 우선순위 큐에 해당 정보를 넣어줍니다.
                    dist[target] = dist[now.index] + w;
                    pq.add(new Element(dist[now.index] + w,target));
                }
            }
        }
        for(int i = 1; i < dist.length;i++){
                System.out.println(dist[i]);
        }
    }
}