[Algorithm] 최소 힙

백준 1927

아래와 같이 '최소 힙' 을 사용하여 문제를 해결하라고 한다. 알고리즘은 공부하고 적으면서 한 번 더 상기시키면 오래 기억에 남으니 적으면서 공부를 해야겠다.

아래 문제와 같이 0이 들어오면 가장 작은 힙을 빼고 재정렬 해야할것이다. 만약 처음부터 0 이 들어오면 그냥 0 을 보내주면 될거같다.

2^31보다 작은 자연수 또는 0이라고 하였다. 음은 주어지지않는다는 말이 있었는데 long 형식으로 해야할거같다는 생각이 들었다.

최소 힙

루트 노드가 최소인 힙

• 값 삽입 과정 : 입력 값을 트리 가장 끝에 위치시키고 부모 노드와 비교하여 부모 노드보다 작다면 부모노드와 위치를 변경한다.
• 값 삭제 과정 : 최상위 노드를 삭제하고 삽입과 반대로 마지막 노드를 위치시키고 자식과 비교하여 위치를 바꾼다.

최대 힙

루트 노드가 최대인 힙

• 값 삽입 과정 : 입력 값을 트리 가장 끝에 위치시키고 부모 노드와 비교하여 부모 노드보다 크다면 부모 노드와 위치를 변경한다.
• 값 삭제 과정 : 최상위 노드를 반환하여 삭제하고 삽입과 반대로 마지막 노드를 위치시켜 자식과 비교하여 위치를 바꾼다.

우선 순위 큐

• 자바Queue를 사용하는 것으로 선입 선출이 아닌 우선순위를 정해두어 poll() 하는것을 우선순위 큐라고 칭한다.

문제 정답

PriorityQueue<Long> queue = new PriorityQueue<>():

위 코드가 있는줄 몰랐다. Queue를 사용했는데 우선순위 큐가 자바에 구현되어있다니 조금 놀랐다. 그리고 조금 실망했다. 이런게 있다면 왜 이제 알았을까라는 스스로 학습량이 부족하다고 느끼기도 한다. 하지만 알았으니 잘 사용해보겠다.

import java.io.*;
import java.util.*;

public class Main {

    public static PriorityQueue<Long> queue = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            long input = Long.parseLong(br.readLine());

            if(input == 0 ) {
                if (queue.isEmpty()) {
                    sb.append("0").append("\n");
                } else {
                    sb.append(queue.poll()).append("\n");
                }
            } else {
                queue.add(input);
            }
        }

        System.out.println(sb);
    }

}

추가

위 우선순위 큐를 일반적으로 사용하면 최소 힙으로 정렬된다 그러면 어떻게 최대힙을 구현할까?

무엇이 바뀌었을까 Collections.reverseOrder()이 추가되었다. 간단하게 구현할 수 있었다!!

import java.io.*;
import java.util.*;

public class Main {

    public static PriorityQueue<Long> queue = new PriorityQueue<>(Collections.reverseOrder());

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            long input = Long.parseLong(br.readLine());

            if(input == 0 ) {
                if (queue.isEmpty()) {
                    sb.append("0").append("\n");
                } else {
                    sb.append(queue.poll()).append("\n");
                }
            } else {
                queue.add(input);
            }
        }

        System.out.println(sb);
    }

}